On the Complexity of Counting Orderings in Graphs
Source: arxiv.org/abs/2606.29157
We study the computational complexity of several counting problems on graphs. Each of these problems consists of counting orderings of the vertices or edges with adjacency constraints. We show $\#P$-completeness for all of them via a common new technique. Given a counting function $C$ of interest, we define a parameterized family of instances $G_q$, where the parameter $q$ controls the amplification of a simple gadget. After multiplying by an explicit factor $f(q)$, we show that the values of $f(q) \cdot C(G_q)$, for positive integers $q$, agree with a rational function in $q$ whose…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.29157
curl -X POST /api/v1/records/arxiv/2606.29157/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.29157/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'