Counting Eulerian circuits in subexponential time, assuming the new #SAT algorithms
Source: hexagonmath.org/abs/2611.00088v1
Counting the Eulerian circuits of an undirected graph is #P-complete, even for planar 4-regular graphs, while for directed graphs the BEST theorem counts them in polynomial time. However, we are unaware of any exact algorithm for undirected graphs of bounded degree that runs in time $2^{o(m)}$, where $m$ is the number of edges. We show that such an algorithm follows from the exact counting of Hamiltonian cycles that we proved earlier on top of Anthropic's claimed #SAT algorithm. The reduction is classical: by Kotzig's description, the Eulerian circuits of $G$ are in bijection with the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00088
curl -X POST /api/v1/records/hexagon/2611.00088/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00088/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'