Counting linear extensions of incidence posets of bipartite graphs is #P-complete
Abstract
Dittmer and Pak proved that counting the linear extensions of the incidence poset I G of a graph G is #P-complete, positively resolving a conjecture in [1] about height-2 posets, and specifically solving a problem mentioned in [7] about incidence posets. We show that the problem remains #P-complete when G is restricted to bipartite graphs; consequently, computing exactly the volume of the McCormick relaxation of a bilinear program is #P-hard. As in their work, we compute the count modulo many primes p, gluing the input to a gadget graph whose own count is known modulo p. Here, the gadget must be bipartite, and we evaluate its residue by a block decomposition of the count modulo p together with a binomial cancellation identity; the same method gives a short proof of the residue of the Dittmer-Pak gadget, correcting a small non-fatal calculation error in their paper. In contrast, we show that the count can be computed in polynomial time for graphs of bounded neighborhood diversity, for example complete bipartite graphs, by a recursion over the numbers of remaining vertices of each type.
Related
- Maximal Linear Arrangement is NP complete on Bipartite Graphs
- Spectral Turán problems for complete bipartite expansions in linear hypergraphs
- Counting quaternion extensions by multi-heights
- Counting Nilpotent Galois extensions with prescribed genus number
- Negative edge correlation in complete bipartite graphs
BibTeX
@misc{lee2026counting,
title = {{Counting linear extensions of incidence posets of bipartite graphs is #P-complete}},
author = {Jon Lee},
howpublished = {HAL},
year = {2026},
month = oct,
url = {https://hal.science/hal-05793069v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Counting linear extensions of incidence posets of bipartite graphs is #P-complete
AU - Jon Lee
PY - 2026
DA - 2026/10/11
PB - HAL
UR - https://hal.science/hal-05793069v1
AB - Dittmer and Pak proved that counting the linear extensions of the incidence poset I G of a graph G is #P-complete, positively resolving a conjecture in [1] about height-2 posets, and specifically solving a problem mentioned in [7] about incidence posets. We show that the problem remains #P-complete when G is restricted to bipartite graphs; consequently, computing exactly the volume of the McCormick relaxation of a bilinear program is #P-hard. As in their work, we compute the count modulo many primes p, gluing the input to a gadget graph whose own count is known modulo p. Here, the gadget must be bipartite, and we evaluate its residue by a block decomposition of the count modulo p together with a binomial cancellation identity; the same method gives a short proof of the residue of the Dittmer-Pak gadget, correcting a small non-fatal calculation error in their paper. In contrast, we show that the count can be computed in polynomial time for graphs of bounded neighborhood diversity, for example complete bipartite graphs, by a recursion over the numbers of remaining vertices of each type.
ER -