The Complexity of Counting Eulerian Tours in 4-regular Graphs

摘要

We investigate the complexity of counting Eulerian tours (#ET) and its variations from two perspectives-the complexity of exact counting and the complexity w.r.t. approximation-preserving reductions (AP-reductions, Dyer et al., Algo-rithmica 38(3):471-500, 2004). We prove that #ET is #P-complete even for planar 4-regular graphs. A closely related problem is that of counting A-trails (#A-TRAILS) in graphs with rotational embedding schemes (so called maps). Kotzig (Theory of Graphs, Proc. Colloq., Tihany, 1966, pp. 219-230, Academic Press, San Diego, 1968) showed that #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 #A-TRAILS in 4-regular maps captures the essence of #ET, that is, we give an AP-reduction from #ET in general graphs to #A-TRAILS in 4-regular maps. The reduction uses a fast mixing result for a card shuffling problem.