PaperlayerView exact revision on arXiv

Source-linked AI summary

Hidden Circuits and Exact Counting in Ordered Graphs

Chenghua Liu, Boning Meng

arXiv:2609.18132v1cs.CCcs.DS

TL;DR

The paper asks which structural restrictions make exact perfect-matching counting tractable, as vertex order can constrain many edges without ensuring small dynamic-programming boundaries. It uses a quantum-circuit-inspired construction and proves hardness on three ordered graph classes, alongside an algorithm for distance-hereditary graphs.

  • Problem

    The paper asks which structural restrictions make exact perfect-matching counting tractable, since ordered representations constrain many edges and may have arbitrarily large overlapping layers.

    Source: §1 · p. 2, §1.3 · p. 9

  • Method

    The reductions use a quantum-circuit-inspired matching construction, with flow and projection arguments for composable Boolean-encoded operations and interpolation across target-operation occurrences.

    Source: §1 · p. 2, §1.3 · p. 10, §3.3 · p. 17

  • Results

    Exact perfect-matching counting is #P-complete under ≤T on monotone, unit interval, and chordal permutation graphs; distance-hereditary graphs have an O(n^2)-arithmetic-operation counting algorithm.

    Source: §1.1 · pp. 2, 4, §1 · p. 2

  • Takeaways & Limitations

    QChains lies strictly within distance-hereditary graphs, and the direct O(n^2) arithmetic algorithm improves the generic O(n^4) bound.

    Source: §1.1 · p. 4

    On larger spaces, normalization can affect later tracks, so the operations cannot be assumed local before the flow and projection arguments.

    Source: §3.3 · p. 17

Abstract

from arXiv · show

We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and chordal permutation graphs. The monotone result settles the exact-counting complexity left open by Dyer, Jerrum, and M\"uller (JACM 2017), complementing their rapid-mixing theorem. Inspired by quantum circuits, our reductions implement a circuit simulation using globally coupled matching-transfer operators. The key construction is an exact projection, implemented by a polynomial-length sequence of normalized transfers, that restores tensor-product locality and makes encoded gates composable. Interpolation-based cancellation then reduces circuit evaluation to unweighted perfect-matching counts in all three classes. We also place Dyer and M\"uller's class QChains within the distance-hereditary graphs and give an $O(n^2)$-arithmetic-operation counting algorithm for the latter, improving the $O(n^4)$ bound obtainable from Curticapean and Marx (SODA 2016). Together with prior results, these advances complete the exact-counting classification of the graph classes in Dyer and M\"uller's diagram (SIDMA 2019).

1 Introduction

The paper resolves open exact-counting questions for graph classes defined by vertex orderings, proving hardness for three ordered classes and giving a faster counting algorithm for distance-hereditary graphs. Together with prior results, these advances complete the exact-counting classification of the classes in Dyer and Müller’s diagram.

1 Introduction

  • Exact counting is studied alongside approximation and sampling, and ordered graph structure is the focus of the paper’s tractability questions.Prior work established rapid mixing on monotone graphs, while exact counting there remained unresolved.Source: §1 · pp. 1–2

1.1 Main results

  • Exact perfect-matching counting is #P-complete under polynomial-time Turing reductions on monotone, unit interval, and chordal permutation graphs.The reductions use simple, unweighted graphs and supply valid interval or permutation representations.Source: §1.1 · pp. 2, 4
  • The hardness results resolve open exact-counting questions for interval, unit interval, convex, biconvex, and monotone graphs.Chordal permutation graphs establish hardness on the intersection of interval and permutation graphs.Source: §1.1 · p. 4
  • An O(n^2)-arithmetic-operation algorithm counts perfect matchings on distance-hereditary graphs after O(n + m) graph preprocessing, improving the generic O(n^4) bound.QChains is a strict subclass of distance-hereditary graphs; the algorithm uses O(n log n)-bit integers.Source: §1.1 · p. 4
  • The new hard cases and the QChains inclusion complete the polynomial-time versus #P-complete classification of Dyer and Müller’s graph-class diagram.The diagram records direct results and consequences by inclusion.Source: §1.1 · p. 4

1.2 Impact on exact counting, sampling, and approximation

The paper contrasts exact counting with sampling and approximation across ordered graph classes, answering open exact-counting questions for several structural restrictions. It also identifies QChains within a tractable larger class and gives a faster counting algorithm for distance-hereditary graphs.

1.2 Impact on exact counting, sampling, and approximation

  • The section frames these results as answers to separate questions about restricted permutations, interval pairings, simultaneous representations, and nested choices.It distinguishes exact-counting results from prior sampling and approximation guarantees.Source: §1.2 · p. 4, §1.2.4 · p. 9

1.2.1 Restricted permutations and monotone constraints

  • Exact counting is #P-complete on monotone graphs, while admissible permutations have an FPAUS and their count has an FPRAS.The exact result settles a question left open after the switch chain was shown to mix rapidly.Source: §1.2.1 · p. 5

1.2.2 Equal-length intervals and nonbipartite sampling

  • Counting pairings of equal-length intervals is #P-complete, although unit interval pairings admit an FPAUS and their count an FPRAS.The hardness also settles exact counting on the containing quasimonotone class; the sampling and approximation guarantees apply there as well.Source: §1.2.2 · pp. 6–7

1.2.3 Simultaneous interval and permutation representations

  • Perfect-matching counting is #P-complete on chordal permutation graphs, even though graphs in this class have both interval and permutation representations.This result establishes hardness within the intersection itself; it does not establish approximation hardness for the class.Source: §1.2.3 · pp. 7–8

1.2.4 Nested choices, exact algorithms, and sampling oracles

  • QChains is contained in the distance-hereditary graphs, where a direct algorithm counts perfect matchings using O(n^2) integer arithmetic operations.The algorithm first uses O(n + m) graph preprocessing and O(n log n)-bit integers; exact uniform sampling follows by self-reduction in expected polynomial time.Source: §1.2.4 · p. 8, Table 4 · p. 9

1.3 A circuit-based approach to ordered counting

The hardness construction turns globally coupled matching transfers into composable operations on encoded bits. An exact projection restores locality, and interpolation and cancellation translate the resulting computation into perfect-matching counts in the target graph classes.

Encoding and projection

  • The projection’s polynomial-length sequence of normalized transfers restores locality, so operations on a few blocks act on their logical bits and leave the others unchanged.The construction uses a non-orthogonal projection and an encoded row space; its composition property is the key to composing gates.Source: §1.3 · pp. 9–10

Interpolation and circuit evaluation

  • A polynomial number of interpolation evaluations recovers forbidden-11 constraints and controlled-sign operations, allowing the construction to count independent sets.Contributions are grouped by multiplicities of constantly many eigenvalues, rather than enumerating choices independently at every gate position.Source: §1.3 · p. 10

Encoding and projection

  • The exact composable encoding is the new step beyond established connections between circuits, matching signatures, tensor contractions, and encoded matchgates.The projection handles the global coupling of ordered transfers.Source: §1.3 · p. 10

Geometric realizations

  • The geometric reductions use probes and interpolation-based cancellation to realize the common paired-layer interface with simple, unweighted graphs in each target class.The constructions compensate for clique edges or complemented cuts; queried probe multiplicities are nonnegative, and cancellation occurs in exact postprocessing.Source: §1.3 · p. 11

Tractable counting

  • On distance-hereditary graphs, the algorithm tracks only the number of active unmatched vertices in each bag and uses O(n^2) integer arithmetic operations.Pendant and twin operations merge bags in O(ab) operations for bag sizes a and b; each original vertex pair is charged at most once.Source: §1.3 · p. 11

1.4 Further context

The section situates ordered-graph counting among exact-counting results for planar, minor-closed, and dense graph classes. It also notes related approximation work and outlines the paper’s organization.

1.4 Further context

  • Planar graphs and minor-closed classes have established exact-counting results, while density alone does not determine tractability.The passage contrasts dense ordered instances with classes that admit exact algorithms, including chain, cochain, threshold, E-free, and cographs.Source: §1.4 · p. 11
  • Related dense-graph work includes hardness for graphs partitionable into two cliques and a subexponential-time algorithm for arbitrary even-order graphs.Matching-polynomial methods also give exact algorithms on cographs.Source: §1.4 · p. 11

1.5 Organization

  • The paper moves from notation and prior results through WordEval and algebraic hardness to three geometric realizations, then gives the structural inclusion and counting algorithm.Source: §1.5 · p. 11

2 Preliminaries

The preliminaries define the graph classes and input models used in the counting results, then establish the complexity, permanent, and interpolation tools used in the reductions.

2.1 Graphs, representations, and the counting problem

  • Unit interval graphs admit equal-length interval representations, and the graph and rational-representation input models for #UnitIntervalPM are polynomial-time equivalent.A representation can be recovered with polynomially bounded coordinates.Source: §2.1 · p. 12

2.2 Permutation diagrams and quasi-classes

  • Permutation diagrams encode adjacency by disagreement between endpoint orders; monotone graphs have nondecreasing interval neighborhoods, and quasi-classes require every cut bipartite graph to belong to the class.QChains is the quasi-class of disjoint unions of chain graphs.Source: §2.2 · p. 13

2.3 Counting complexity and the source problem

  • Polynomial-time Turing reductions may combine exact oracle answers arithmetically, and counting independent sets is #P-complete by the bipartite vertex-cover result.The paper's reduction uses rational coefficients and cancellations while every queried graph remains unweighted.Source: §2.3 · p. 14

2.4 Permanents and matrix notation

  • For bipartite graphs, the permanent of the biadjacency matrix equals the perfect-matching count, while projections are idempotent matrices whose rank equals their trace.Weighted edge assignments give the corresponding weighted sum over perfect matchings.Source: §2.4 · pp. 14–15

2.5 Exact interpolation

  • Exact interpolation recovers a degree-at-most-d rational polynomial from d+1 distinct rational evaluations in polynomial time when degrees and binary lengths are polynomially bounded.A constant number of successive interpolations retains polynomial complexity.Source: §2.5 · p. 15

3 WordEval and layered perfect matchings

The paper represents layered perfect-matching counts as products of subset-state transfer matrices. It then encodes operations as words in normalized transfers and reduces their evaluation to unweighted layered matching counts by interpolation.

3.1 Subset states and permanental transfers

  • Subset states record occupied tracks, and permanental-compound transfers count weighted bijections across a cut, with a complement operator accounting for vertices reserved for the next layer.Multiplying transfers sums over intermediate states, with each perfect matching represented by a unique state sequence.Source: §3.1 · pp. 15–16, §3.2 · p. 16

3.2 Reading a perfect matching one layer at a time

  • In the layered graph, the perfect-matching count is the product of cut transfers between boundary states, and every cut has p matching edges.At an internal layer, the next state's vertices remain available to the right, so the current cut covers their complement.Source: §3.2 · p. 16, Figure 2 · p. 16

3.3 Four normalized operations and WordEval

  • The operations R_i, D_i, B_i, and E_i are defined by normalized perturbations of the upper-triangular transfer, but their global actions are not automatically local.The normalization removes the background transfer; separate flow and projection arguments make the Boolean-encoded actions composable.Source: §3.3 · p. 17
  • WordEval entries have polynomial bit length because the upper-triangular transfer is unitriangular and its nilpotent deviation has a polynomially bounded index.The paper bounds the nilpotence index using the subset-weight range, rather than the exponentially large state-space dimension.Source: §3.3 · pp. 17–18

3.4 A common paired-transfer interface

  • PairEval realizes word evaluation through paired cut transfers; interpolation at −1 recovers the desired entry using polynomially many unweighted perfect-matching queries.For a word of length g, Lemma 3.3 uses gp^2 + 1 instances, each with h = g(t + 1) pairs for 0 ≤ t ≤ gp^2.Source: §3.4 · pp. 19–20

4 One-way flow and restriction to a block

The normalized operations obey one-way flow across track prefixes. This monotonicity implies that a word restricted to a block cannot increase its particle count there, and count-preserving transitions act locally within the block.

4 One-way flow and restriction to a block

  • A transition is rightward when no prefix count increases, where each prefix count records the occupied tracks before a cut.The elementary operations R, D, B, and E satisfy these one-way flow constraints.Source: §4 · p. 20
  • For a word using only indices within a block, any nonzero transition cannot increase the block's particle count.The inequality persists across a product because each operation obeys the same boundary-flow restriction.Source: §4 · p. 21
  • When a transition preserves the block count, its coefficient is the local word's coefficient and exterior occupations must remain unchanged.The diagonal restrictions of the normalized operations factor as tensor products across the block and its exterior.Source: §4 · p. 22

5 A polynomial-length encoding projection

A four-track filter selects a two-state encoding, and a stabilized global filter becomes a projection. Projected operations then recover locality and compose as encoded gates.

5.1 A four-track filter

  • The four-track filter annihilates the zero- and one-particle sectors and is an idempotent rank-two map on the two-particle sector.It fixes the two code rows 1010 and 0110, used for logical zero and one.Source: §5.1 · pp. 22–23

5.2 Stabilization of the global filter

  • For k blocks, the global filter's sufficiently high power is an idempotent projection of rank 2^k.Its word length is O(k^3) times a known scalar, and stabilization follows because only the all-two-particle block has a nonzero diagonal block.Source: §5.2 · pp. 23–24

5.3 The encoded action and its locality

  • The global projection can retain off-diagonal contributions, but its image has rank 2^k and supports encoding and recovery maps satisfying P_k = L_kE_k.The encoded row space need not equal the span of the raw code states.Source: §5.2 · p. 24, §5.3 · p. 25
  • After projection, an operation confined to r blocks acts as its isolated local word on those blocks and as the filter on every outside block.Retaining the intervening projections makes the encoded logical operations compose.Source: §5.3 · p. 25

6 Constant-size operations on the encoding

The section defines rational linear circuits on logical bits and gives constant-size transfer constructions for encoded one- and two-bit operations. The resulting fixed matrices provide the operations used to compose these circuits.

6 Constant-size operations on the encoding

  • Logical circuits are explicitly listed products of one- and two-bit rational matrices, whose gates may be noninvertible and need not map each input to a single output.Circuit evaluation specifies an entry of the product.Source: §6 · p. 26
  • One-bit encoded actions include c B1 = Q, c D2 = A, and bT = 8X.Here Q = diag(2, 1) and A = diag(−1, 1/2).Source: §6 · p. 26
  • The encoded one- and two-bit matrices are obtained by direct calculation on four or eight tracks, and the same matrices can be placed at each block or adjacent block pair.The two-bit construction uses C2 to select four specified tracks.Source: §6 · p. 26
  • Equation (21) implements the products using a constant number of raw letters and projections, while retaining their scalar normalizations explicitly.Powers of Q are products of projected copies; general words require justification before scalar factors can be moved outside powers.Source: §6 · pp. 26–27

7 Shared-parameter interpolation of constraints

The section removes off-diagonal entries and obtains other diagonal constraints through shared-parameter interpolation. These reductions preserve exact evaluation using polynomially many oracle calls and polynomial-time postprocessing.

7.1 Removing the off-diagonal entries

  • CircuitEval({∆}) reduces to WordEval by implementing sampled gates with polynomial-length words and inserting projections between successive gates.The construction uses N = 4k tracks and known rational scalar normalizations.Source: §7.1 · p. 28
  • A shared parameter q makes the selected circuit entry a polynomial of degree at most two per occurrence, and evaluating at q = 2u allows interpolation at zero.Other gates, including H, may occur anywhere without changing the degree argument.Source: §7.1 · p. 28
  • The interpolation samples, scalar factors, oracle answers, and exact postprocessing all have polynomial bit length.These bounds permit recovery of the desired entry in polynomial time.Source: §7.1 · p. 28

7.2 Two diagonal constraints from powers of ∆

  • CircuitEval({N, CZ}) reduces to CircuitEval({∆}) by replacing each target constraint with powers of ∆ and interpolating over a shared grid.The two target types use separate parameters when both occur; the grid size is polynomial, even when gates are interleaved.Source: §7.2 · p. 29
  • Grouping intermediate-state paths by their state counts makes the interpolation restore all occurrences of the chosen constraint simultaneously.Distinct prime-factorization values distinguish the groups, and polynomial bit-length bounds make the exact postprocessing feasible.Source: §7.2 · p. 29

8 The algebraic counting reduction

The reduction encodes independent-set counting as circuit evaluation, then transfers its hardness through WordEval to PairEval. Since #IS is #P-complete, both evaluation problems are #P-hard.

8.1 Counting independent sets

  • Each source-graph edge applies N to its endpoint bits, imposing the constraint that the endpoints are not both selected.The circuit begins with one logical bit per vertex, initially zero, and concludes by summing assignment coefficients.Source: §8.1 · p. 30
  • Adjacent exchanges bring nonadjacent endpoint bits together, with each exchange implemented by three CZ operations and six H operations at scalar normalization 1/8.No final restoration of the variable order is needed.Source: §8.1 · p. 30
  • The construction uses O(km) gates, and its normalization factors have polynomial bit length.The all-zero to all-zero circuit entry yields the independent-set count after normalization.Source: §8.1 · p. 30

8.2 Algebraic hardness

  • #IS reduces to WordEval and then PairEval, making both evaluation problems #P-hard.The first reduction composes the independent-set construction with the two interpolation lemmas; the second is Lemma 3.3.Source: §8.2 · p. 30

9 Monotone graphs

Paired probes and interpolation reduce PairEval to unweighted perfect-matching counts on monotone graphs. The construction also supplies explicit permutation and monotone representations for its query graphs.

9 Monotone graphs

  • #PM(Monotone) is #P-complete under polynomial-time Turing reductions.The construction reduces PairEval to monotone-graph perfect-matching counts, and membership follows from polynomial-time verification of a canonical matching encoding.Source: §9 · p. 31, §9.3 · p. 35

9.1 A bipartite probe identity

  • A paired bipartite probe contributes a polynomial in its size parameter whose value at s = −1 gives the weighted matching cancellation identity.At s = −1, the contribution counts bijections between prescribed original vertex sets with added-edge weight −1.Source: §9.1 · p. 32

9.2 The query graph and its endpoint orders

  • The query graph uses independent original layers and paired probe classes, with cut matrices Mr and 1 − Hr.The endpoint orders yield both a bipartite permutation representation and a monotone ordering.Source: §9 · p. 31, §9.2 · pp. 32–33
  • Endpoint orders realize the prescribed cuts and probe connections while preventing edges between nonconsecutive original layers or different probe pairs.The construction deletes unwanted boundary vertices from both orders.Source: §9.2 · p. 33

9.3 Interpolation and the oracle reduction

  • Using one probe-size parameter for all pairs, 2ph + 1 samples suffice to interpolate the target value while every oracle query remains simple and unweighted.At s = −1, each second cut acquires weight −1 and each first cut remains unchanged; all target matchings have the same sign (−1)^ph.Source: §9.3 · p. 34
  • The reduction's normalization and rational interpolation are polynomial-time exact computations, yielding PairEval ≤T #PM(Monotone).The endpoint orders and monotone ordering are explicit.Source: §9.3 · p. 35

10 Unit interval graphs

The section reduces paired-transfer evaluation to perfect-matching counts on unit interval graphs, using clique layers and interpolation-based cancellation. This yields #P-completeness for exact perfect-matching counting on unit interval graphs.

10.1 An equal-length realization of the pairs

  • Clique layers realize paired cuts using a first cut of 1 − M and a second cut of H in an equal-length interval representation.Profiles are adjusted to realize the prescribed cut comparisons while retaining an explicit integer-endpoint representation.Source: §10.1 · p. 35, Table 5 · p. 36

10.2 Clique cancellation using equal-length probes

  • Replacing each probe with s identical copies makes normalized matching counts polynomial in s, and evaluation at s = −1 cancels intralayer edges while preserving the second cut.At the first cut, 1 − M becomes −M; interpolation recovers the desired paired-transfer value.Source: §10.2 · p. 37, Figure 7 · p. 38
  • The reduction uses n0/2 + 1 interpolation queries, with polynomial-size graphs, endpoints, and exact arithmetic.The queries at s = 0, 2, …, n0 determine the normalized polynomial at −1.Source: §10.2 · p. 37
  • Exact perfect-matching counting on unit interval graphs is #P-complete.The reduction is a polynomial-time Turing reduction from PairEval.Source: §10 · p. 35, §10.2 · p. 38

11 Chordal permutation graphs

The section constructs chordal permutation graphs whose matching counts recover paired-transfer evaluations. Private probes cancel clique-layer edges without sacrificing either the permutation representation or chordality.

11.2 Cancellation and the oracle reduction

  • Exact perfect-matching counting on chordal permutation graphs is #P-complete under polynomial-time Turing reductions.The construction explicitly supplies a permutation representation for each oracle graph.Source: §11 · p. 39, §11.2 · p. 42

11.1 A representation with one private probe per layer

  • Clique layers and private probes realize the prescribed cut matrices while retaining a two-order permutation representation.Each probe is adjacent to exactly one layer, and the layers have no edges between nonconsecutive pairs.Source: §11.1 · pp. 39–40
  • Replacing each probe by a clique of s vertices preserves the permutation representation, and every resulting graph Gs is chordal.The proof establishes chordality by eliminating probe vertices first, then the original layers in neighborhood-inclusion order.Source: §11.1 · p. 40

11.2 Cancellation and the oracle reduction

  • Interpolation at s = −1 cancels intralayer edges while leaving cut edges unchanged, recovering the independent-layer transfer graph.Using the samples s = 0, 2, …, n0 requires n0/2 + 1 queries.Source: §11.2 · pp. 41–42, Figure 8 · p. 41

12 Exact counting in quasi-chain graphs

The section places QChains properly inside the distance-hereditary graphs and gives a direct perfect-matching algorithm for the larger class. Its pruning-based bag dynamic program uses O(n^2) arithmetic operations after linear-time graph processing.

12 Exact counting in quasi-chain graphs

  • QChains is a proper subclass of distance-hereditary graphs, as its forbidden pre-P5 condition excludes the distance-hereditary obstructions while P5 itself witnesses strictness.This inclusion brings QChains within the scope of the distance-hereditary counting algorithm.Source: §12 · pp. 42–43, Figure 9 · p. 43

12.3 A quadratic arithmetic implementation

  • For distance-hereditary graphs, perfect matchings can be counted in O(n^2) arithmetic operations on O(n log n)-bit integers after O(n + m) graph processing.The direct algorithm improves on the O(n^4) bound obtainable from the cited generic clique-width result.Source: §12 · p. 43

12.1 Pruning and the boundary of a bag

  • The algorithm processes pendant and twin deletions by merging bags, whose active vertices share the same neighborhood outside their bag.Only the number of uncovered active vertices is stored; other vertices in the bag have no neighbors outside it.Source: §12.1 · pp. 43–44

12.2 The three merge operations

  • False-twin merges have no cross-bag matching edges, true-twin merges count choices and bijections between uncovered vertices, and pendant merges must cover the pendant-side boundary.The merge updates preserve the bag and matching-state invariants.Source: §12.2 · pp. 44–46

12.3 A quadratic arithmetic implementation

  • Each merge costs O(ab) arithmetic operations for bags of sizes a and b, and charging each vertex pair at its first shared bag bounds total work by O(n^2).The implementation evaluates the true-twin operation in O(ab) integer arithmetic operations.Source: §12.3 · pp. 46–47
Loading 2609.18132v1…