Pith. sign in

REVIEW 2 major objections 5 minor 108 references

Complexity and Geometry of Sampling Connected Graph Partitions

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Uniformly sampling connected 2-partitions is intractable on maximal plane graphs of degree at most 531, assuming RP is not NP, and the standard flip walk can take exponential time on explicit bounded-degree examples.

desk verdict Solid intractability and mixing-time results for connected graph partition sampling; the empirical section is illustrative, and one small repairable gap appears in the bounded-degree reduction. read the letter →

arxiv 1908.08881 v1 pith:QMHPM6EV submitted 2019-08-23 cs.CC cs.CYcs.DMmath.CO

Elle Najt , Daryl DeFord , Justin Solomon This is my paper · ORCID
classification cs.CCcs.CYcs.DMmath.CO MSC 05C8568Q1705C4568W2060J10
keywords connectedgraphpartitionsuniformsamplingcomputationalintractabilityMarkovchainmixingflipwalkplanegraphsHamiltoniancyclereductionredistricting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper is about the difficulty of sampling graph partitions whose pieces are connected. Its central claim is that, assuming $\mathrm{RP}\ne\mathrm{NP}$, there is no polynomial-time algorithm that uniformly samples connected 2-partitions, even when the graph is required to be a maximal plane graph of vertex degree at most 531, and that the same holds for $\epsilon$-balanced 2-partitions and for certain weighted families of $k$-partitions. The intractability is established by reductions that concentrate sampling probability onto Hamiltonian cycles: a sampler that is only slightly non-uniform can be converted into an RP algorithm for an NP-complete decision problem. On the algorithmic side, the paper shows that the flip walk Markov chain used by practitioners can mix exponentially slowly, with a concrete maximal plane graph family of degree at most 9 whose mixing time is at least $5^d/250$. It also identifies positive cases: on series-parallel graphs and graphs of bounded treewidth, uniform and balanced sampling can be done in polynomial time, which is noteworthy because the flip walk remains slow on some of those graphs. The motivation is redistricting, where ensemble methods compare a proposed districting plan to random alternatives and depend on exactly the sampling algorithms the paper puts under suspicion.

What carries the argument

The load-bearing machinery is the 'lucky guess' reduction template: to prove a sampling problem intractable, one builds a polynomial-time map $B$ that embeds a hard decision problem into the sampling space, together with a projection $\pi$ such that a uniformly random sample lands, with probability at least $1-1/m$, on a solution of the hard problem; an $\alpha$-almost sampler then becomes an RP algorithm. The concrete gadgets are the chain of bigons, which replaces each edge by $d$ parallel pairs and gives $2^d$ routings through an edge, and, for bounded degree, the vertex-replacement gadget $R_d$, which has $\Theta(5^d)$ simple boundary links between its three terminals. A plane-duality bijection between simple cycles of the dual and connected 2-partitions carries these cycle results over to partitions. For the flip walk, the bottleneck sets are fibers of a restriction map: in the doubled $d$-star graph $D_d(H)$, a fiber has at most $(d+1)n2^{(\mathrm{cut}-1)d}$ boundary edges against $2^{d\,\mathrm{cut}}$ elements; for $T_d(G)=(R_d(G^*))^*$, partitions are classified by whether original triangles are pure or mixed, and the boundary of the set of all-mixed partitions is exponentially small relative to its size.

What would settle it

A polynomial-time probabilistic algorithm that samples connected 2-partitions of every maximal plane graph of degree at most 531 within total variation distance $\alpha<1$ would directly contradict Theorem 2.45, since the proof would then give an RP algorithm for an NP-complete language and hence $\mathrm{RP}=\mathrm{NP}$. Short of resolving that conjecture, one can test the finite claims by exhaustively enumerating $P_2(H_d)$ for small $d$, computing exact mixing times, and checking whether they respect the bound $5^d/250$ and whether the fiber-size counts in the bottleneck lemmas are correct.

Watch

Extended reading notes

Core claim

Read in good faith, the paper's core discovery is that uniformly sampling connected 2-partitions is intractable in a strong topological sense, and that the mechanism behind the intractability is explicit. Theorem 2.45 states that if a polynomial-time probabilistic machine $\alpha$-almost samples $P_2(G)$ uniformly for every maximal plane graph $G$ of maximum degree at most 531, for any $\alpha<1$, then $\mathrm{RP}=\mathrm{NP}$. The proof uses plane duality: connected 2-partitions of $G$ are in bijection with simple cycles of the dual $G^*$, and a vertex-replacement construction ($G \mapsto R_d(G)$) concentrates the uniform measure on Hamiltonian cycles. Corollary 3.18 gives a family $H_d$ of maximal plane graphs of degree at most 9 for which the flip walk on $P_2(H_d)$ has mixing time at least $5^d/250$, exponential in the number of vertices. The same machinery yields intractability for $\epsilon$-balanced 2-partitions and for weighted connected $k$-partitions. Against this, the paper proves positive results: on series-parallel graphs there are polynomial-time dynamic programs that sample uniformly from $P_2(G)$ and from balanced 2-partitions, and the underlying counting problems are fixed-parameter tractable in treewidth.

Load-bearing premise

The load-bearing unproven premise is the conjecture that randomized polynomial time and nondeterministic polynomial time are not equal ($\mathrm{RP}\ne\mathrm{NP}$); every negative theorem in the paper is conditional, asserting that a polynomial-time sampler would force $\mathrm{RP}=\mathrm{NP}$. The reductions also inherit Hamiltonian-cycle NP-completeness results proved in other papers, so the chain is only as strong as those external theorems and the conjecture.

Editorial extensions

If this is right

  • If the central claim is right, no general polynomial-time sampler exists for connected 2-partitions of planar graphs, so algorithms used in ensemble redistricting analysis must either exploit special graph structure or give up uniformity guarantees.
  • Balanced partitions, which are the version most relevant to redistricting, are no easier: $\epsilon$-balanced uniform 2-partition sampling is intractable on 2-connected plane graphs for every fixed $\epsilon\ge 0$.
  • The flip walk, despite being irreducible and having uniform stationary distribution on 2-connected graphs, can miss large regions of the state space for exponentially long times, even on bounded-degree maximal plane graphs.
  • The tractable cases are genuinely different: series-parallel graphs admit polynomial-time samplers for $P_2$ and balanced $P_2$, so intractability is not universal, but the flip walk can still be slow there.
  • For fixed $\lambda\in(0,1]$, sampling connected $k$-partitions with weight $\lambda^{|\mathrm{cut}|}$ is also intractable on 2-connected planar graphs, extending the difficulty beyond the uniform case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the conditional intractability is taken seriously, then any sampler used on real state-dual graphs must be validated on the specific graph rather than trusted as a black box; the paper's bottlenecks suggest a concrete diagnostic, namely tracking which vertices or triangles almost never flip.
  • The self-avoiding-walk connection points to an extension the authors do not pursue: outlier conclusions from $\nu_\lambda$ ensembles may switch abruptly near the critical fugacity $\lambda=1/\mu$, so sensitivity analysis over $\lambda$ and over graph discretization could be as important as mixing-time guarantees.
  • A natural testable extension is to search for pure-triangle bottlenecks in flip walks on real dual graphs, including non-triangulated ones; if analogous bottlenecks appear, the empirical relevance of Corollary 3.18 would be stronger than the worst-case framing suggests.
  • Because the positive results are parameterized by treewidth, and state dual graphs typically have high treewidth, the gap suggests looking for other structural parameters under which connected-partition sampling might become tractable.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies the complexity of sampling connected k-partitions of planar graphs and the mixing behavior of the flip-walk Markov chain used in redistricting. It proves conditional intractability results: uniform sampling of P2(G) is intractable on plane graphs; balanced 2-partition sampling is intractable on 2-connected plane graphs; P2 sampling remains intractable on maximal plane graphs of maximum degree at most 531; and weighted k-partition sampling is intractable for fixed λ∈(0,1]. It also constructs explicit families of graphs on which the flip walk mixes exponentially slowly, and it provides empirical evidence of slow mixing and of sensitivity to graph discretization. On the positive side, the paper gives polynomial-time samplers for series-parallel graphs and fixed-parameter tractable algorithms in treewidth, with details in the appendix.

Significance. If the results hold, they provide a strong negative answer to a question underlying statistical redistricting: no polynomial-time uniform sampler exists unless RP=NP, and the standard MCMC heuristic can fail torpidly even on heavily constrained planar graphs. The paper is unusually careful in its proof structure: the reductions are built from explicit gadgets (bigons, Rd, dipoles) with counting lemmas and probability-concentration bounds, the positive algorithms are specified with correctness arguments in the appendix, and the experimental code is publicly available. The main limitation is that all hardness statements are conditional on RP≠NP, which the paper clearly flags. The bounded-degree result is the strongest and most useful contribution for practice.

major comments (2)
  1. [§2.5.1, Proposition 2.33 and Theorem 2.25] The proof of Theorem 2.25 does not establish the stated constant. Proposition 2.33 proves termination of Algorithm 2.2 only for d≥178, so the output graph is guaranteed to have maximum face degree at most 178, not at most 177. Since Corollary 2.44 and Theorem 2.45 use the C177 bound to derive the maximum degree 531, the stated bound is not proved as written. The energy calculation in the proof of Proposition 2.33 appears to give a negative decrease for faces of degree f=178, so the missing step is a verification for threshold d=177; alternatively, the constants can be shifted to C178 and degree 534. This is a small but load-bearing repair.
  2. [§2.1, Lemma 2.8 and Algorithm 2.1] The lucky-guess reduction does not explicitly use the acceptance/rejection behavior of the α-almost sampler. Definition 2.4 allows the machine to reject with probability up to 1/2, but Algorithm 2.1 and its proof treat G as though it always returns a sample, and q is silently a conditional distribution. The proof can be fixed by returning NO when G rejects and replacing 'success with probability at least 1/m' by 'at least 1/(2m)', which is still a positive constant for fixed α. Because the lemma is used in every hardness result, this formal detail should be corrected.
minor comments (5)
  1. [§2.5.1, Proposition 2.33] The text first says the energy function starts with value O(n^2) and then bounds the initial energy by O(|V(H)|^4); for cubic 3CCP graphs the correct bound is O(|V|^2), so one of these statements should be corrected.
  2. [§2.5.3, Theorem 2.43] The symbol d is used both for the face-degree parameter in C_d and for the gadget size in R_d(G) within the same proof; this overloaded notation should be disambiguated, for example by calling the gadget size r.
  3. [§4] The empirical claims of slow mixing are based on single-run traces and visual inspection; the text already frames these as evidence rather than proof, but it should state more explicitly that no convergence diagnostics or repeated-run variability is provided.
  4. [§5] There are duplicate theorem numbers: Theorem 5.2 appears in §5.1 and again in §5.4.1, and Theorem 5.1 in §5.4 conflicts with the numbering sequence. The theorem environment should be renumbered.
  5. [§5.3, Lemma 5.5] The remainder bound R_d is written with the factor d n^2 in the displayed inequality after being introduced as 2^{d(|J|-1)}2^{n^2}+d|J|; the derivation of the displayed form should be made explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central hardness and mixing theorems reduce to external NP-completeness results and are internally derived.

full rationale

The derivation chain is not circular. The main intractability results (Theorems 2.15, 2.21, 2.45, 2.68/2.69) are conditional reductions: they define intractability relative to RP != NP (Definition 2.6), invoke the Jerrum-Valiant-Vazirani lucky-guess lemma (Lemma 2.8), and reduce from external NP-completeness results ([49] for Hamiltonian cycles on 3CCP graphs, [93] for maximal plane graphs, [59] for grid graphs). The probability-concentration gadgets (chains of bigons, the Rd construction, and dipole chains) are original constructions whose growth rates are proved by recurrence (Theorem 2.37) or direct counting, and the target partition distributions are never used to define these gadgets. The flip-walk bottlenecks in Section 3 are independent conductance calculations using those same gadgets, and the positive results in Section 5 are derivations from counting via division-with-remainder, not from the hardness claims. Self-citations ([17], [36], [41], [91]) appear only in contextual or forward-looking remarks and are not load-bearing for any theorem. I also note, as a correctness issue unrelated to circularity, that Proposition 2.33 states termination for d >= 178 while Theorem 2.25 claims face degree at most 177; the energy computation appears repairable, but this is a proof gap rather than an instance of the argument assuming its own conclusion.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central theorems rest on the standard RP != NP conjecture and on external NP-completeness theorems and classical graph facts. The new gadgets are fully specified constructions with proofs of their counting and boundary behavior; no additional unexplained entities are introduced. Empirical parameters such as lambda are chosen from the self-avoiding walk literature and are not fitted to the reported curves.

assumptions (7)
  • domain assumption RP != NP
    Adopted in Definition 2.6 as the definition of intractability for sampling; all negative sampling results are conditional on it.
  • standard math Hamiltonian cycle is NP-complete on 3-connected cubic plane graphs (C-HAM NP-complete)
    External theorem [49], restated as Theorem 2.26 and used as the base for the bounded-face-degree hardness Theorem 2.25.
  • standard math Hamiltonian cycle is NP-complete on grid graphs
    External theorem [59], used in Proposition 2.57 to prove PlanarMaxEdgesDualkPartition NP-complete.
  • standard math Grinberg's theorem: every Hamiltonian cycle in a maximal plane graph separates faces into equal total weight
    Used in Lemma 2.19 to show Hamiltonian cycles of maximal plane graphs are balanced, giving probability concentration for balanced simple cycle sampling.
  • standard math Gyori-Lovasz theorem: every 2-connected graph admits a balanced connected 2-partition
    Used in Section 2.4 to ensure balanced sampling instances on 2-connected graphs are non-vacuous.
  • standard math Courcelle-style MSO2 counting meta-theorem for bounded-treewidth graphs
    Used in Section 5.4 to show counting and sampling connected k-partitions is FPT in treewidth.
  • domain assumption Existence and value of square-lattice connective constant mu and SAW phase transition at lambda = 1/mu
    Used to choose lambda in the empirical experiments in Section 4.2; it motivates but does not prove the main theorems.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity and Geometry of Sampling Connected Graph Partitions." pith.science (2026). https://pith.science/paper/QMHPM6EV

@misc{pith2026190808881,
  author       = {Pith},
  title        = {Pith review of: Complexity and Geometry of Sampling Connected Graph Partitions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QMHPM6EV}},
  note         = {Machine review of arXiv:1908.08881}
}
read the original abstract

In this paper, we prove intractability results about sampling from the set of partitions of a planar graph into connected components. Our proofs are motivated by a technique introduced by Jerrum, Valiant, and Vazirani. Moreover, we use gadgets inspired by their technique to provide families of graphs where the "flip walk" Markov chain used in practice for this sampling task exhibits exponentially slow mixing. Supporting our theoretical results we present some empirical evidence demonstrating the slow mixing of the flip walk on grid graphs and on real data. Inspired by connections to the statistical physics of self-avoiding walks, we investigate the sensitivity of certain popular sampling algorithms to the graph topology. Finally, we discuss a few cases where the sampling problem is tractable. Applications to political redistricting have recently brought increased attention to this problem, and we articulate open questions about this application that are highlighted by our results.

Figures

Figures reproduced from arXiv: 1908.08881 by the authors.

Figure 1.1
Figure 1.1. a) Kansas with county units [25], along with a connected 2-partition. b) The corresponding state dual graph overlayed. Much more granular subdivisions of a state are often used. the flip walk state space [12]. We will discuss other related work in the body of the paper, such as the connection to self-avoiding walks (§4.1), and related sampling problems (§3.1). 1.2. Basic Notation. Let G = (V, E) be a graph; unless o… view at source ↗
Figure 1
Figure 1. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2.1
Figure 2.1. The directed version from [63] and its undirected bigons counter part. Certain calculations appear repeatedly when checking the probability concentration hypothesis of Lemma 2.8. We isolate them here: Lemma 2.9. If H, N ≥ 0 and H ≥ DN for some D > 0, then H H+N ≥ D 1+D . Lemma 2.10. Fix q ≥ 2. Then for any e ∈ N and S ≥ 1 if d ≥ 2 and d ≥ 4(log2 (S)+e log2 (q) ) 2 then q d ≥ Sde . Proof. It suffices to pick d so tha… view at source ↗
Figures from the paper (37 more)
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png]
Figure 2.2
Figure 2.2. Figure 2.2: The 3OR gadget. See Figure A.1 in the appendix for more detail. The distinguished attaching nodes are colored red [PITH_FULL_IMAGE:figures/full_fig_p010_2_2.png]
Figure 2.3
Figure 2.3. Figure 2.3: Inserting a 3OR. See Figure A.1 for more detail. Lemma 2.29. Let H be a 3CCP graph, F a face of H, and {e1, e2, e3} edges of H. Construct a graph H0 by attaching a 3OR gadget to the edges {e1, e2, e3}. Then H0 has a Hamiltonian cycle if and only if H has a Hamiltonia…
Figure 2.4
Figure 2.4. Figure 2.4: The first 3 terms in the sequence of gadgets. [PITH_FULL_IMAGE:figures/full_fig_p012_2_4.png]
Figure 2.5
Figure 2.5. Figure 2.5: The node labels in the recursive construction [PITH_FULL_IMAGE:figures/full_fig_p012_2_5.png]
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p012_2.png]
Figure 2.6
Figure 2.6. Figure 2.6: The decompositions used for Equation (2.4) and Equation (2.6). The Sd (resp. Dd) part is in red. Observe that there are two options for the simple path Rd[Cd], one of which is colored blue. useful when computing |SC(Rn)| and |SBL(Rn)|: Definition 2.36 (Simple paths f…
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p013_2.png]
Figure 2.7
Figure 2.7. Figure 2.7: a) The five ways to extend an element of [PITH_FULL_IMAGE:figures/full_fig_p014_2_7.png]
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p016_2.png]
Figure 2.8
Figure 2.8. Figure 2.8: A step in the reduction in Proposition 2.57 2.6.3. The Chain of Dipoles Construction, Degeneration of k-Partitions. We will concern ourselves with the following sampling problem, where we fix λ > 0: λ-sampling connected dual k-partitions Input: A graph G. Output: An …
Figure 2.9
Figure 2.9. Figure 2.9: Example of degeneration and subtle non-degeneration. [PITH_FULL_IMAGE:figures/full_fig_p017_2_9.png]
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p017_2.png]
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p018_2.png]
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p020_3.png]
Figure 3.1
Figure 3.1. Figure 3.1: The chain of bigons construction and its dual [PITH_FULL_IMAGE:figures/full_fig_p022_3_1.png]
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p022_3.png]
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p023_3.png]
Figure 3.2
Figure 3.2. Figure 3.2: A snapshot of the flip walk evolving, illustrating the bottleneck of [PITH_FULL_IMAGE:figures/full_fig_p024_3_2.png]
Figure 3.3
Figure 3.3. Figure 3.3: The affect of T2 3.5. Bottlenecks from the Rd construction. The example of Theorem 3.11 is not entirely satisfying, for example because the degrees of its nodes increase without bound. We will address some of its weaknesses in this section by producing a family of ma…
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p024_3.png]
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p025_3.png]
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p026_3.png]
Figure 4.1
Figure 4.1. Figure 4.1 [PITH_FULL_IMAGE:figures/full_fig_p026_4_1.png]
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p026_4.png]
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p027_4.png]
Figure 4.2
Figure 4.2. Figure 4.2: These examples start from an upper left to bottom right diagonal partition of a 40 [PITH_FULL_IMAGE:figures/full_fig_p028_4_2.png]
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p028_4.png]
Figure 4.3
Figure 4.3. Figure 4.3: Two measurements of a single run. AP D = 90%, x = 1, steps = 194, 390, 536, started from a vertical partition into red and blue blocks. a) Each node displays the color of its average block: more red if frequently in the red block, and more blue if frequently in the b…
Figure 4.5
Figure 4.5. Figure 4.5: Frankengraph. The top is is a triangular lattice and bottom is a square lattice. Both pieces are [PITH_FULL_IMAGE:figures/full_fig_p029_4_5.png]
Figure 4.4
Figure 4.4. Figure 4.4: Two runs of flip walk based MCMC on the state dual graph of Kansas. Top: Starting plan. Middle: Counting Flips. Bottom: Ending plan [PITH_FULL_IMAGE:figures/full_fig_p030_4_4.png]
Figure 4.6
Figure 4.6. Figure 4.6: A flip walk based MCMC run with λ = 1/2, starting from the diagonal partition of the Franken￾graph. 90% population constraint. 17, 768, 956, 990 steps. 30 [PITH_FULL_IMAGE:figures/full_fig_p030_4_6.png]
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p031_4.png]
Figure 4.7
Figure 4.7. Figure 4.7: An edge is yellower if it is more frequently a cut-edge of sampled partition. The left hand [PITH_FULL_IMAGE:figures/full_fig_p032_4_7.png]
Figure 4.8
Figure 4.8. Figure 4.8: 1000 samples, on a 36 × 36 node graph. Each half gate is 6 × width vertices long, so width 3 represents the gate cutting the graph entirely in half. The numbers reported are obtained in the following way: some nodes are set to be 1 and others to 0. Each district majo…
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p039_4.png]
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p040_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

108 extracted references · 74 canonical work pages

  1. [1]

    Replication code, https://github.com/LorenzoNajt/Code-For-Complexity-and-Geometry-of-Sampling-Connected-Graph-Partitions

  2. [2]

    Stack exchange answer , https://cstheory.stackexchange.com/a/41367/44995

  3. [3]

    Stack exchange answer , https://cstheory.stackexchange.com/a/42567/44995

  4. [4]

    Stack exchange answer , https://mathoverflow.net/a/313003/41873

  5. [5]

    Stack exchange answer , https://cstheory.stackexchange.com/a/43865/44995

  6. [6]

    Stack exchange answer and discussion , https://cstheory.stackexchange.com/a/41272/44995

  7. [7]

    Stack exchange comment , https://cstheory.stackexchange.com/q/41998/44995

  8. [8]

    Stack exchange comments , https://mathoverflow.net/q/316132/41873

Show all 108 references
  1. [9]

    Stack exchange question , https://cstheory.stackexchange.com/q/44338/44995. 41

  2. [10]

    Aaronson, P ?= NP, in Open problems in mathematics, Springer, 2016, pp

    S. Aaronson, P ?= NP, in Open problems in mathematics, Springer, 2016, pp. 1–122

    2016

  3. [11]

    Abbott and D

    H. Abbott and D. Hanson , A lattice path problem , Ars Combinatoria, 6 (1978), pp. 163–178

    1978

  4. [12]

    H. A. Akitaya, M. D. Jones, M. Korman, C. Meierfrankenfeld, M. J. Munje, D. L. Souvaine, M. Thramann, and C. D. T ´oth, Reconfiguration of connected graph partitions, arXiv preprint arXiv:1902.10765, (2019)

    2019 arXiv

  5. [13]

    Altman, Is automation the answer: The computational complexity of automated redistricting , Rutgers Computer and Law Technology Journal, 23 (1997)

    M. Altman, Is automation the answer: The computational complexity of automated redistricting , Rutgers Computer and Law Technology Journal, 23 (1997)

    1997

  6. [14]

    Arnborg, J

    S. Arnborg, J. Lagergren, and D. Seese , Easy problems for tree-decomposable graphs , Journal of Algorithms, 12 (1991), pp. 308–340

    1991

  7. [15]

    Arora and B

    S. Arora and B. Barak , Computational complexity: a modern approach , Cambridge University Press, 2009

    2009

  8. [16]

    Bangia, C

    S. Bangia, C. V. Graves, G. Herschlag, H. S. Kang, J. Luo, J. C. Mattingly, and R. Ravier , Redistricting: Drawing the Line , arXiv:1704.03360 [stat], (2017), http://arxiv.org/abs/1704.03360

    2017 arXiv

  9. [17]

    Bar-Natan, L

    A. Bar-Natan, L. Najt, and Z. Schutzman, The gerrymandering jumble: Map projections permute districts’ compact- ness scores, arXiv preprint arXiv:1905.03173, (2019)

    2019 arXiv

  10. [18]

    Barnes and J

    R. Barnes and J. Solomon , Gerrymandering and compactness: Implementation flexibility and abuse , arXiv preprint arXiv:1803.02857, (2018)

    2018 arXiv

  11. [19]

    D. W. Barnette, On steinitz’s theorem concerning convex 3-polytopes and on some properties of planar graphs , in The many facets of graph theory, Springer, 1969, pp. 27–40

    1969

  12. [20]

    Berg´e, B

    P. Berg´e, B. Mouscadet, A. Rimmel, and J. Tomasik , Fixed-parameter tractability of counting small minimum (s,t )- cuts, arXiv preprint arXiv:1907.02353, (2019)

    2019 arXiv

  13. [21]

    Bez´akov´a, E

    I. Bez´akov´a, E. W. Chambers, and K. Fox , Integrating and sampling cuts in bounded treewidth graphs , in Advances in the Mathematical Sciences, Springer, 2016, pp. 401–415

    2016

  14. [22]

    H. L. Bodlaender and B. De Fluiter , Parallel algorithms for series parallel graphs , in European Symposium on Algorithms, Springer, 1996, pp. 277–289

    1996

  15. [23]

    Bouchitt´e, F

    V. Bouchitt´e, F. Mazoit, and I. Todinca , Treewidth of planar graphs: connections with duality , in Euroconference on Combinatorics, Graph Theory and Applications, vol. 10, 2001, pp. 34–38

    2001

  16. [24]

    Bousquet-M´elou, A

    M. Bousquet-M´elou, A. J. Guttmann, and I. Jensen , Self-avoiding walks crossing a square , Journal of Physics A: Mathematical and General, 38 (2005), p. 9159

    2005

  17. [25]

    U. C. Bureau, Tiger/line shapefiles, 2010, https://www2.census.gov/geo/tiger/TIGER2010/

    2010

  18. [26]

    Caldera, D

    S. Caldera, D. DeFord, M. Duchin, S. C. Gutekunst, and C. Nix , Mathematics of nested districts: The case of alaska, (2019), https://mggg.org/uploads/Alaska.pdf

    2019

  19. [27]

    E. W. Chambers, K. Fox, and A. Nayyeri , Counting and sampling minimum cuts in genus g graphs, Discrete & Computational Geometry, 52 (2014), pp. 450–475

    2014

  20. [28]

    G.-U. E. Charles et al. , Amicus brief of mathematicians, law professors, and students in support of the appellees and affirmance, https://mggg.org/SCOTUS-MathBrief.pdf

  21. [29]

    Chen, Expert report of Jowei Chen, ph.d

    J. Chen, Expert report of Jowei Chen, ph.d. , Raleigh Wake Citizen’s Association et al. vs. The Wake County Board of Elections, (2017), https://www.pubintlaw.org/wp-content/uploads/2017/06/Expert-Report-Jowei-Chen.pdf

    2017

  22. [30]

    Chen and J

    J. Chen and J. Rodden , Unintentional Gerrymandering: Political Geography and Electoral Bias in Legislatures , Quarterly Journal of Political Science, 8 (2013), pp. 239–269, https://www.nowpublishers.com/article/Details/ QJPS-12033

    2013

  23. [31]

    Chikina, A

    M. Chikina, A. Frieze, and W. Pegden , Assessing significance in a Markov chain without mixing , Proceedings of the National Academy of Sciences, 114 (2017), pp. 2860–2864, http://www.pnas.org/content/114/11/2860

    2017

  24. [32]

    Cho and Y

    W. Cho and Y. Liu , Toward a Talismanic Redistricting Tool: A Computational Method for Identifying Extreme Redis- tricting Plans, Election Law Journal: Rules, Politics, and Policy, 15 (2016)

    2016

  25. [33]

    W. K. T. Cho and Y. Y. Liu , Sampling from complicated and unknown distributions: Monte Carlo and Markov Chain Monte Carlo methods for redistricting, Physica A: Statistical Mechanics and its Applications, 506 (2018), pp. 170–178, http://www.sciencedirect.com/science/article/pi...

    2018

  26. [34]

    Courcelle and J

    B. Courcelle and J. Engelfriet , Graph structure and monadic second-order logic: a language-theoretic approach , vol. 138, Cambridge University Press, 2012

    2012

  27. [35]

    Cygan, F

    M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh , Parameterized algorithms, vol. 4, Springer, 2015

    2015

  28. [36]

    DeFord and M

    D. DeFord and M. Duchin , Redistricting reform in virginia: Districting criteria in context , Virginia Policy Review, 12(2) (2019), pp. 120–146

    2019

  29. [37]

    DeFord, H

    D. DeFord, H. Lavenant, Z. Schutzman, and J. Solomon , Total Variation Isoperimetric Profiles , arXiv:1809.07943 [cs, math], (2018), http://arxiv.org/abs/1809.07943

    2018 arXiv

  30. [38]

    E. D. Demaine and M. Hajiaghayi, The bidimensionality theory and its algorithmic applications, The Computer Journal, 51 (2008), pp. 292–302

    2008

  31. [39]

    E. D. Demaine, M. Hajiaghayi, and D. M. Thilikos, The bidimensional theory of bounded-genus graphs, in International Symposium on Mathematical Foundations of Computer Science, Springer, 2004, pp. 191–203

    2004

  32. [40]

    T. S. C. O. P. M. District , League of women voters of pennsylvania v. the commonwealth of pennsylvania , https: //www.brennancenter.org/sites/default/files/legal-work/LWV v PA Majority-Opinion.pdf

  33. [41]

    Duchin, D

    M. Duchin, D. DeFord, and J. Solomon , Recombination: A family of markov chains for redistricting (forthcoming)

  34. [42]

    Duchin and B

    M. Duchin and B. E. Tenner , Discrete geometry for electoral geography, arXiv preprint arXiv:1808.05860, (2018)

    2018 arXiv

  35. [43]

    Duminil-Copin, G

    H. Duminil-Copin, G. Kozma, and A. Yadin , Supercritical self-avoiding walks are space-filling , in Annales de l’IHP Probabilit´ es et statistiques, vol. 50, 2014, pp. 315–326

    2014

  36. [44]

    Duminil-Copin and S

    H. Duminil-Copin and S. Smirnov, The connective constant of the honeycomb lattice equals √ 2 + √ 2, Annals of Math- ematics, 175 (2012), pp. 1653–1665. 42

    2012

  37. [45]

    Dyer and A

    M. Dyer and A. Frieze , On the complexity of partitioning graphs into connected subgraphs , Discrete Applied Mathe- matics, 10 (1985), pp. 139–153, http://linkinghub.elsevier.com/retrieve/pii/0166218X85900083

    1985

  38. [46]

    Ebbinghaus, J

    H.-D. Ebbinghaus, J. Flum, and W. Thomas , Mathematical logic, Springer Science & Business Media, 2013

    2013

  39. [47]

    Erickson, Planar graphs, http://jeffe.cs.illinois.edu/teaching/comptop/chapters/02-planar-graphs.pdf

    J. Erickson, Planar graphs, http://jeffe.cs.illinois.edu/teaching/comptop/chapters/02-planar-graphs.pdf

  40. [48]

    Frick and M

    M. Frick and M. Grohe , The complexity of first-order and monadic second-order logic revisited , Annals of pure and applied logic, 130 (2004), pp. 3–31

    2004

  41. [49]

    Garey, D

    M. Garey, D. Johnson, and R. Tarjan , The Planar Hamiltonian Circuit Problem is NP-Complete , SIAM Journal on Computing, 5 (1976), pp. 704–714, https://epubs.siam.org/doi/10.1137/0205049

    1976 doi

  42. [50]

    Gelman and C

    A. Gelman and C. Hennig, Beyond subjective and objective in statistics , Journal of the Royal Statistical Society: Series A (Statistics in Society), 180 (2017), pp. 967–1033

    2017

  43. [51]

    Grinbergs, On planar regular graphs degree three without hamiltonian cycles , (2009), https://arxiv.org/abs/arXiv: 0908.2563

    E. Grinbergs, On planar regular graphs degree three without hamiltonian cycles , (2009), https://arxiv.org/abs/arXiv: 0908.2563

    2009 arXiv

  44. [52]

    Große, J

    A. Große, J. Rothe, and G. Wechsung , Relating partial and complete solutions and the complexity of computing smallest solutions , in Italian Conference on Theoretical Computer Science, Springer, 2001, pp. 339–356

    2001

  45. [53]

    Gy˝ori, On division of graphs to connected subgraphs , North-Holland Publ

    E. Gy˝ori, On division of graphs to connected subgraphs , North-Holland Publ. Comp, Amsterdam ; Oxford ; New York, 1978, pp. 485 – 494

    1978

  46. [54]

    Herschlag, H

    G. Herschlag, H. S. Kang, J. Luo, C. V. Graves, S. Bangia, R. Ravier, and J. C. Mattingly , Quantifying Gerry- mandering in North Carolina , (2018), http://arxiv.org/abs/1801.03783

    2018 arXiv

  47. [55]

    Herschlag, R

    G. Herschlag, R. Ravier, and J. C. Mattingly, Evaluating Partisan Gerrymandering in Wisconsin , arXiv:1709.01596 [physics, stat], (2017), http://arxiv.org/abs/1709.01596

    2017 arXiv

  48. [56]

    T. R. Hoens, Counting and sampling paths in graphs , (2008)

    2008

  49. [57]

    T. R. Hunter, The first gerrymander? Patrick Henry, James Madison, James Monroe, and Virginia’s 1788 congressional districting, Early American Studies, (2011), pp. 781–820

    2011

  50. [58]

    Impagliazzo and A

    R. Impagliazzo and A. Wigderson, P = BPP unless E has subexponential circuits: derandomizing the XOR lemma , in Proceedings of the 29th STOC, 1997, pp. 220–229

    1997

  51. [59]

    A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter, Hamilton paths in grid graphs , SIAM Journal on Computing, 11 (1982), pp. 676–686

    1982

  52. [60]

    T. Ito, X. Zhou, and T. Nishizeki, Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size, Journal of discrete algorithms, 4 (2006), pp. 142–154

    2006

  53. [61]

    Jensen, A parallel algorithm for the enumeration of self-avoiding polygons on the square lattice , Journal of Physics A: Mathematical and General, 36 (2003), p

    I. Jensen, A parallel algorithm for the enumeration of self-avoiding polygons on the square lattice , Journal of Physics A: Mathematical and General, 36 (2003), p. 5731

    2003

  54. [62]

    Jensen, Improved lower bounds on the connective constants for two-dimensional self-avoiding walks , Journal of Physics A: Mathematical and General, 37 (2004), p

    I. Jensen, Improved lower bounds on the connective constants for two-dimensional self-avoiding walks , Journal of Physics A: Mathematical and General, 37 (2004), p. 11521

    2004

  55. [63]

    M. R. Jerrum, L. G. Valiant, and V. V. Vazirani , Random generation of combinatorial structures from a uniform distribution, Theoretical Computer Science, 43 (1986), pp. 169–188, http://www.sciencedirect.com/science/article/ pii/030439758690174X

    1986

  56. [64]

    Kennedy, Monte carlo tests of stochastic loewner evolution predictions for the 2d self-avoiding walk , Physical review letters, 88 (2002), p

    T. Kennedy, Monte carlo tests of stochastic loewner evolution predictions for the 2d self-avoiding walk , Physical review letters, 88 (2002), p. 130601

    2002

  57. [65]

    Kenyon, The asymptotic determinant of the discrete laplacian , Acta Mathematica, 185 (2000), pp

    R. Kenyon, The asymptotic determinant of the discrete laplacian , Acta Mathematica, 185 (2000), pp. 239–286

    2000

  58. [66]

    Khuller and V

    S. Khuller and V. V. Vazirani , Planar graph coloring is not self-reducible, assuming P ⁄= NP, Theoretical Computer Science, 88 (1991), pp. 183–189

    1991

  59. [67]

    Kueng, D

    R. Kueng, D. G. Mixon, and S. Villar , Fair redistricting is hard, Theoretical Computer Science, (2019)

    2019

  60. [68]

    Lapoire, Treewidth and duality for planar hypergraphs

    D. Lapoire, Treewidth and duality for planar hypergraphs. , (1996)

    1996

  61. [69]

    G. F. Lawler, O. Schramm, and W. Werner , On the scaling limit of planar self-avoiding walk , arXiv preprint math/0204277, (2002)

    2002 arXiv

  62. [70]

    D. A. Levin, Y. Peres, and E. L. Wilmer , Markov Chains and Mixing Times , American Mathematical Soc., 2009

    2009

  63. [71]

    Y. Y. Liu, W. K. T. Cho, and S. Wang , PEAR: a massively parallel evolutionary computation approach for political redistricting optimization and analysis , Swarm and Evolutionary Computation, 30 (2016), pp. 78–92, http://www. sciencedirect.com/science/article/pii/S2210650216300220

    2016

  64. [72]

    Lovasz, A homology theory for spanning tress of a graph , Acta Mathematica Hungarica, 30 (1977), pp

    L. Lovasz, A homology theory for spanning tress of a graph , Acta Mathematica Hungarica, 30 (1977), pp. 241–251

    1977

  65. [73]

    Madras , Critical behaviour of self-avoiding walks: that cross a square , Journal of Physics A: Mathematical and General, 28 (1995), p

    N. Madras , Critical behaviour of self-avoiding walks: that cross a square , Journal of Physics A: Mathematical and General, 28 (1995), p. 1535

    1995

  66. [74]

    Madras and G

    N. Madras and G. Slade , The self-avoiding walk , Springer Science & Business Media, 1996

    1996

  67. [75]

    D. B. Magleby and D. B. Mosesson , A New Approach for Developing Neutral Redistricting Plans , Political Analysis, 26 (2018), pp. 147–167

    2018

  68. [76]

    K. C. Martis, The original gerrymander , Political Geography, 8 (2008), pp. 833–839

    2008

  69. [77]

    Mattingly, Declaration of Jonathan Mattingly, Common Cause vs

    J. Mattingly, Declaration of Jonathan Mattingly, Common Cause vs. Rucho, (2017), http://s10294.pcdn.co/wp-content/ uploads/2016/05/Expert-Report-of-Jonathan-Mattingly.pdf

    2017

  70. [78]

    Montanari and P

    S. Montanari and P. Penna , On sampling simple paths in planar graphs according to their lengths , in International Symposium on Mathematical Foundations of Computer Science, Springer, 2015, pp. 493–504

    2015

  71. [79]

    T. M. D. of North Carolina , Common cause v. rucho , https://www.brennancenter.org/sites/default/files/legal-work/ 2018-08-27-142-Memorandum%20Opinion.pdf

    2018

  72. [80]

    Pegden, Pennsylvania’s congressional districting is an outlier: Expert report , League of Women Voters vs

    W. Pegden, Pennsylvania’s congressional districting is an outlier: Expert report , League of Women Voters vs. Pennsyl- vania General Assembly, (2017), https://www.brennancenter.org/sites/default/files/legal-work/LWV v PA Expert Report WesleyPegden 11.17.17.pdf

    2017

  73. [81]

    P¨onitz and P

    A. P¨onitz and P. Tittmann , Improved upper bounds for self-avoiding walks in zd , Electron. J. Combin, 7 (2000). 43

    2000

  74. [82]

    Randall and A

    D. Randall and A. Sinclair, Self-testing algorithms for self-avoiding walks , Journal of Mathematical Physics, 41 (2000), pp. 1570–1584

    2000

  75. [83]

    J. M. Schmidt, Structure and constructions of 3-connected graphs , PhD thesis, 2011

    2011

  76. [84]

    Shoup, A computational introduction to number theory and algebra , Cambridge university press, 2009

    V. Shoup, A computational introduction to number theory and algebra , Cambridge university press, 2009

    2009

  77. [85]

    A. J. Sinclair, Randomised algorithms for counting and generating combinatorial structures , (1988)

    1988

  78. [86]

    A. D. Sokal , How to beat critical slowing-down: 1990 update , Nuclear Physics B-Proceedings Supplements, 20 (1991), pp. 55–67

    1991

  79. [87]

    A. D. Sokal, Monte carlo methods for the self-avoiding walk , arXiv preprint hep-lat/9405016, (1994)

    1994 arXiv

  80. [88]

    A. D. Sokal and L. E. Thomas , Absence of mass gap for a class of stochastic contour models , Journal of Statistical Physics, 51 (1988), pp. 907–947

    1988

  81. [89]

    A. D. Sokal and L. E. Thomas , Exponential convergence to equilibrium for a class of random-walk models , Journal of Statistical Physics, 54 (1989), pp. 797–828

    1989

  82. [90]

    Suzuki, N

    H. Suzuki, N. Takahashi, and T. Nishizeki , A linear algorithm for bipartition of biconnected graphs , Information Processing Letters, 33 (1990), pp. 227–231

    1990

  83. [91]

    I. S. Vicente and L. Najt, Practical algorithms for counting and sampling simple cycles for graphs of bounded tree-width, (Forthcoming)

  84. [92]

    J. A. Wald and C. J. Colbourn, Steiner trees, partial 2-trees, and minimum ifi networks , Networks, 13 (1983), pp. 159– 167

    1983

  85. [93]

    Wigderson, The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs , 1982, https://www

    A. Wigderson, The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs , 1982, https://www. math.ias.edu/avi/node/820

    1982

  86. [94]

    D. B. Wilson , Generating random spanning trees more quickly than the cover time , in STOC, vol. 96, Citeseer, 1996, pp. 296–303

    1996

  87. [95]

    U. S. D. C. F. T. W. D. O. Wisconsin , Whitford v. gill , https://www.brennancenter.org/sites/default/files/legal-work/ Whitford-Opinion112116.pdf. 44 Appendix A. Appendix for complexity results. e1 e2 Pocket LargeFace LargeFace AdjacentFace Adjacent Face Adjacent Face e3 Figur...

  88. [96]

    This can be lifted to a path between x and y in A(G)\{a,b}

    If C(x)⁄= v and C(y)⁄= v, then there is a path between C(x) and C(y) in G\{C(a),C (b)}, since G is 3-connected. This can be lifted to a path between x and y in A(G)\{a,b}

  89. [97]

    There are three cases: (a) If |L∩{a,b}| = 0: As A′ is 3-connected, there is a path in A′\ (B∩{a,b}) from x to w

    If C(x) =v, it is always possible to find a path in A(G)\{a,b} fromx to some x′ withC(x′)⁄=v. There are three cases: (a) If |L∩{a,b}| = 0: As A′ is 3-connected, there is a path in A′\ (B∩{a,b}) from x to w. This gives a path in A(G) from x to a node L. (b) If |L∩{a,b}| = 1: At ...

  90. [98]

    Can you recover a connected partition from its edge boundary?

  91. [99]

    What does the edge boundary of a partition of a plane graph look like in the dual graph?

  92. [100]

    In what way is the number of blocks of a connected partition reflected in its representation in the dual graph? We state and prove the theorems that answer these questions in the next three subsections, and the end result is Theorem 2.52. The reader may note that 1) is answered...

  93. [101]

    There is a block containing σ, ϵ and τ

  94. [102]

    There is a block containing σ and ϵ, and a distinct block containing τ

  95. [103]

    There is a block containing σ, and a distinct block containing ϵ and τ

  96. [104]

    This accounts for 4 of the 5 equivalence relations on{σ,ϵ,τ}

    σ,ϵ and τ are each in a different block. This accounts for 4 of the 5 equivalence relations on{σ,ϵ,τ}. The missing equivalence relation on{σ,ϵ,τ} would putσ andτ in a block, and ϵ in a different block. This case cannot occur due to the requirement that the blocks are connected. ...

  97. [105]

    Z1 has a path through G1 and G2 from σ to τ

  98. [106]

    Z1 has a path through only G1 from σ to τ

  99. [107]

    Z1 has a path through only G2 from σ to τ

  100. [108]

    No paths, that is: σ∈Z1 and τ∈Z3. One can now observe that for each Z = (Z1,Z 2,Z 3), Z can be produced in exactly one of the four cases in Algorithm B.4, because each case is distinguished what kind of paths in Z1 there are from σ toτ. Moreover, because the Xi andYi can be re...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.