2010/09/25 by Qi Ge, Ge, Qi, Daniel Stefankovic +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1009.5019
arxiv created 2010/09/25 · arxiv updated 2010/09/28
We investigate the complexity of counting Eulerian tours (\sc #ET) and its variations from two perspectives---the complexity of exact counting and the complexity w.r.t. approximation-preserving reductions (AP-reductions \citeMR2044886). We prove that \sc #ET is #P-complete even for planar 4-regular graphs. A closely related problem is that of counting A-trails (\sc #A-trails) in graphs with rotational embedding schemes (so called maps). Kotzig \citeMR0248043 showed that \sc #A-trails can be computed in polynomial time for 4-regular plane graphs (embedding in the plane is equivalent to giving a rotational embedding scheme). We show that for 4-regular maps the problem is #P-hard. Moreover, we show that from the approximation viewpoint \sc #A-trails in 4-regular maps captures the essence of \sc #ET, that is, we give an AP-reduction from \sc #ET in general graphs to \sc #A-trails in 4-regular maps. The reduction uses a fast mixing result for a card shuffling problem \citeMR2023023. In order to understand whether #\sc A-trails in 4-regular maps can AP-reduce to #\sc ET in 4-regular graphs, we investigate a problem in which transitions in vertices are weighted (this generalizes both #\sc A-trails and #\sc ET). In the 4-regular case we show that \sc A-trails can be used to simulate any vertex weights and provide evidence that \sc ET can simulate only a limited set of vertex weights.