Pith. sign in

REVIEW 6 minor 43 references

Enumerating $k$-arc-connected orientations

T0 review · 0 major / 6 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 Every k-arc-connected orientation of a graph can be listed exactly once by a quadratic-time backtracking algorithm.

desk verdict A solid enumeration paper: simple algorithms for k-arc-connected orientations with O(knm^2) delay and O(m^2) amortized time; the central proof holds up, with only minor presentational fixes needed. read the letter →

arxiv 1908.02050 v5 pith:CKBNGTWE submitted 2019-08-06 math.CO cs.DM

Sarah Blind , Kolja Knauer , Petru Valicov This is my paper · ORCID
classification math.COcs.DM MSC 05C2005C4005C85
keywords k-arc-connectedorientationsorientationenumerationalpha-orientationsoutdegreesequencesbacktracksearchflippablepathsamortizedtimecyclereversals
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 asks whether every k-arc-connected orientation of an undirected graph can be enumerated without repetition, and answers affirmatively with two backtracking algorithms. The first is easy to state but relies on submodular-flow feasibility checks. The second, simpler algorithm splits the task into two independent enumeration problems: listing all orientations with a prescribed outdegree sequence (the $\alpha$-orientations), and listing all outdegree sequences attained by k-connected orientations. For the combined Algorithm 4 the paper proves a delay of $O(k n m^2)$ between outputs and, for $k\ge 2$, an amortized time of $O(m^2)$, improving over the submodular-flow approach's analysis. A reader should care because this turns enumeration of a parameterized connectivity class into a structured search whose building blocks are reusable for tilings, matchings, and other combinatorial families modeled by $\alpha$-orientations.

What carries the argument

The central object is the flippable pair $(u,v)$: in a $k$-connected orientation, $u$ and $v$ form a flippable pair when the maximum number of arc-disjoint directed paths from $u$ to $v$ is more than $k$, so reversing any directed $u$-to-$v$ path lowers the arc connectivity of no pair below $k$. Lemma 10 asserts that for any target $k$-connected outdegree sequence, a vertex with outdegree below its target can always be increased one unit by flipping such a path from some vertex whose outdegree is above target. The other ingredient is the cycle-reversal characterization of $\alpha$-orientations: two orientations have the same outdegree sequence exactly when they differ by reversing arc-disjoint directed cycles, which makes the inner enumeration a directed-path test inside a backtrack tree. The cycle-space dimension lower bound supplies enough same-sequence orientations for the amortized time argument.

What would settle it

Search for two $k$-connected orientations $D$ and $D'$ of a multigraph and a vertex $v$ with $\delta^+_D(v)<\delta^+_{D'}(v)$ such that no vertex $u$ with $\delta^+_D(u)>\delta^+_{D'}(u)$ has $\lambda_D(u,v)>k$; Lemma 8 shows such a $(u,v)$ is exactly the flippable pair Lemma 10 needs. Finding one would make Lemma 10 false and Algorithm 3 miss the outdegree sequence of $D'$. Alternatively, brute-force enumerate all $k$-connected orientations of a small $2k$-edge-connected graph and compare Algorithm 4's output list against them to detect a missing orientation.

Watch

Extended reading notes

Core claim

The central claim is Theorem 15: Algorithm 4 enumerates all $k$-arc-connected orientations of a graph $G$ exactly once, with time delay $O(k n m^2)$, and with amortized time $O(m^2)$ whenever $k\ge 2$. The algorithm reaches every orientation by moving along two kinds of reversals. Reversing a directed cycle changes the orientation but keeps the outdegree sequence fixed, so all orientations of one sequence can be listed by cycle flips. Reversing a directed path between a vertex with surplus outdegree and a vertex with deficit raises the deficit vertex's outdegree by one while preserving $k$-connectivity, provided the pair is flippable; Lemma 10 guarantees such a pair always exists when the target sequence is attainable. The amortized improvement comes from Lemma 14, which shows each $k$-connected outdegree sequence supports at least $(k-1)n + 2$ orientations, so the sequence-level work is averaged over many orientation-level outputs.

Load-bearing premise

The load-bearing premise is Lemma 10: from any $k$-connected orientation, a vertex whose outdegree must be raised can always be raised by one unit by reversing a directed path from some vertex with surplus outdegree, without ever dropping below $k$-connectivity; if this failed for some multigraph, the search tree could skip entire outdegree sequences.

Editorial extensions

If this is right

  • Algorithm 4 lists every $k$-arc-connected orientation with no repetitions, with $O(k n m^2)$ delay; for $k\ge 2$ the amortized time per orientation is $O(m^2)$, a direct improvement over the submodular-flow-based Algorithm 1's $O(m(k^3 n^3 + k n^2 m))$ delay.
  • The $\alpha$-orientation subroutine enumerates all orientations with a fixed outdegree sequence in $O(m^2)$ delay, so any object class encoded as $\alpha$-orientations, such as domino tilings or perfect matchings of plane bipartite graphs, inherits this listing bound whenever it can be reduced to the same problem.
  • The outdegree-sequence routine enumerates every $k$-connected outdegree sequence in $O(k n m^2)$ delay and can be reused as the outer loop whenever the target family is closed under directed-cycle reversals once a sequence is fixed.
  • The search-tree partition by fixed arcs and fixed vertices makes each output appear exactly once, so no post-filtering or deduplication is needed.
  • For $k\ge 2$, the amortized bound shows that the sequence-level enumeration cost is negligible on average, because each outdegree sequence has many orientations attached to it.

Reading between the lines

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

  • The paper's cycle-flip and path-flip split is a general enumeration template: any connectivity-style property that is invariant under directed-cycle reversals and preserved by flippable path reversals could be enumerated with the same two-level backtrack structure, not just $k$-arc-connectivity.
  • The amortized bound depends on having many orientations per outdegree sequence; for $k=1$ the lower bound is only $2$, which is why the $O(m^2)$ amortized statement starts at $k\ge 2$. Improving the lower bound or treating $k=1$ separately would be a natural test of how far the averaging argument stretches.
  • A practical extension would replace the repeated BFS flippability checks with incremental all-pairs connectivity data, potentially reducing the per-node cost below $O(km)$ and improving the delay term for large $k$.
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

0 major / 6 minor

Summary. The paper addresses the enumeration of k-arc-connected orientations of a loopless multigraph, listing each orientation exactly once. It first gives a straightforward backtrack algorithm (Algorithm 1) based on a submodular-flow feasibility test with delay O(m(k^3n^3+kn^2m)). The main contribution is Algorithm 4, which splits the problem into (i) enumerating all outdegree sequences attained by k-connected orientations via flippable directed-path reversals (Section 5, Algorithm 3) and (ii) enumerating all orientations with a prescribed outdegree sequence by reversing directed cycles (Section 4, Algorithm 2). Theorem 15 claims Algorithm 4 has O(knm^2) time delay and O(m^2) amortized time for k≥2. The central technical ingredient is Lemma 10, which asserts that whenever a current k-connected orientation has lower outdegree at v than a target k-connected orientation, some flippable pair (u,v) exists, allowing v's outdegree to be increased by one.

Significance. The paper's main claims appear correct and are proved in a largely self-contained way once standard tools (Menger's theorem, submodularity of directed cut functions, and directed cycle-space generation) are admitted. Lemma 10 is load-bearing and survives close inspection: the uncrossing of tight sets and the counting over the disjoint maximal tight sets and their complement are valid, so the inductive correctness of Algorithm 3 is not endangered by the existential choice of u. Lemma 14's cycle-space lower bound supports the claimed k-independent amortized bound. The α-orientation enumeration in Section 4 is a clean result of independent interest. The paper is transparent about the cost of finding an initial k-connected orientation and about limitations for vertex-connectivity variants. I see no circularity: the complexity bounds are derived from external benchmarks, and self-citations are only background.

minor comments (6)
  1. [Section 5, before Observation 1] The sentence 'reverse a directed path P_uv from u to v and thus increase δ_D^+(u) by one, decrease δ_D^+(v) by one' has the endpoints swapped; the correct effect, as Observation 1 and Algorithm 3 use, is that u's outdegree decreases and v's outdegree increases.
  2. [Lemma 5, proof and complexity paragraph] The direction of the path is reversed in two places: the proof should say that the absence of a directed path from v to u (not from u to v) in D\F prevents an α-orientation fixing F and reversing a=(u,v), and the BFS should be from v to u, matching the path P in the algorithm.
  3. [Abstract and Theorem 15] The abstract states 'amortized time O(m^2)' without the qualification that this holds for k≥2; Theorem 15 explicitly requires k≥2, so the abstract should carry the same caveat.
  4. [Algorithm 4] Algorithm 4 uses the helper functions Reverse− and Reverse+ but does not redefine them; as printed, the versions from Algorithm 3 call EnODS and would output outdegree sequences instead of orientations. The authors should state explicitly that these helpers are to be replaced by versions calling EnODS′.
  5. [Preliminaries] The paper should specify that k is a positive integer; for k=0 several of the complexity and degree arguments, such as 'in a k-connected orientation we have kn≤m' and the k≥2 amortized bound, would need separate treatment or become degenerate.
  6. [Introduction and general editing] There are several typographical errors, for example 'th same outdegrees' and 'revering a directed triangle'; these should be corrected before final publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation chain is self-contained; the central claims do not reduce to their inputs.

full rationale

The paper's central chain is: Lemma 4 (cycle reversals characterize equal outdegree sequences), Lemma 7 (k-connectivity is invariant within O_alpha), Lemma 8 (path reversal lowers the endpoint pair's lambda by exactly one), Lemma 9 (flippability is testable by k+1 BFS), Lemma 10 (existence of a flippable pair when one outdegree is too low), Lemma 12 (EnODS enumerates k-connected outdegree sequences), Theorem 6 (EnOPODS enumerates alpha-orientations), and Theorem 15 (combining the two). Each step is proved in the text from Menger's theorem, submodularity of directed cut functions, the standard cycle-space dimension bound, and the handshaking identity. Lemma 10, the load-bearing existence lemma, is proved directly: intersecting tight sets are shown to be disjoint via submodularity of the directed cut function, and the counting over the maximal tight sets plus Y = V \ union X yields a strict inequality that contradicts the equality c = c. No step defines its target in terms of itself, no fitted parameter is renamed as a prediction, and no central premise rests on the authors' own prior work. Self-citations are not load-bearing: [4] is background discussion of submodular-flow implementations, and [29] is a standard textbook result for the cycle-space dimension with stated assumptions, independent of the present algorithms. The runtime claims are complexity analyses of explicit backtracking algorithms, not empirical predictions. Hence there is no circular step.

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

The paper introduces no free parameters or invented entities. Its claims rest on standard structural results (Menger, Nash-Williams, Frank's transformation theorem, cycle space dimension) and on cited polynomial-time subroutines for finding initial orientations. All are external to the paper and independently established.

assumptions (6)
  • domain assumption Nash-Williams theorem: G admits a k-connected orientation iff G is 2k-edge connected
    States the existence condition for k-connected orientations in the Introduction; used as background for the problem.
  • domain assumption Frank's transformation theorem [19]: any two k-connected orientations can be transformed into each other by reversals of directed paths and directed cycles
    Conceptual basis for splitting enumeration into α-orientations and outdegree sequences in Sections 4-6.
  • standard math Local Menger theorem for digraphs (Theorem 1 in the paper)
    Used in Lemmas 8, 9, and 10 to relate cut sizes to arc-disjoint paths.
  • standard math Submodularity of directed cut functions
    Used in Lemma 10's proof to show maximal tight sets are disjoint.
  • standard math Cycle space of a weakly connected digraph has dimension m-n+1 and is generated by directed cycles in strongly connected digraphs
    Used in Lemma 14 to lower-bound the number of α-orientations per outdegree sequence.
  • domain assumption Existence of polynomial-time algorithms for finding a k-connected orientation and an initial α-orientation (submodular flow / max flow)
    Used as preprocessing subroutines in Algorithms 2, 3, 4; complexity cited from [28], [15], [36].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Enumerating $k$-arc-connected orientations." pith.science (2026). https://pith.science/paper/CKBNGTWE

@misc{pith2026190802050,
  author       = {Pith},
  title        = {Pith review of: Enumerating $k$-arc-connected orientations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CKBNGTWE}},
  note         = {Machine review of arXiv:1908.02050}
}
abstract

We study the problem of enumerating the $k$-arc-connected orientations of a graph $G$, i.e., generating each exactly once. A first algorithm using submodular flow optimization is easy to state, but intricate to implement. In a second approach we present a simple algorithm with $O(knm^2)$ time delay and amortized time $O(m^2)$, which improves over the analysis of the submodular flow algorithm. As ingredients, we obtain enumeration algorithms for the $\alpha$-orientations of a graph $G$ in $O(m^2)$ time delay and for the outdegree sequences attained by $k$-arc-connected orientations of $G$ in $O(knm^2)$ time delay.

Figures

Figures reproduced from arXiv: 1908.02050 by the authors.

Figure 1
Figure 1. Three strongly connected orientations. Only those in the middle and on the right side are [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages

  1. [1]

    Flipdistancesbetweengraphorientations

    Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, andBirgitVogtenhuber. Flipdistancesbetweengraphorientations. InIgnasiSauandDimitriosM. Thilikos, editors, Graph-Theoretic Concepts in Computer Science, pages 120–134, Cham, 2019. Springer International Publishing

    work page 2019

  2. [2]

    Completing orientations of partially oriented graphs

    Joergen Bang-Jensen, Jing Huang, and Xuding Zhu. Completing orientations of partially oriented graphs. Journal of Graph Theory, 87(3):285–304, 2018

    work page 2018

  3. [3]

    Barbosa and Jayme L

    Valmir C. Barbosa and Jayme L. Szwarcfiter. Generating all the acyclic orientations of an undi- rected graph. Information Processing Letters, 72(1):71 – 74, 1999

    work page 1999

  4. [4]

    Output-sensitive algorithms for enumeration problems in graphs

    Sarah Blind. Output-sensitive algorithms for enumeration problems in graphs. PhD thesis, Uni- versité de Lorraine, 2019

    work page 2019

  5. [5]

    3-orientations and Schnyder-3-tree-decompositions, 2000

    Enno Brehm. 3-orientations and Schnyder-3-tree-decompositions, 2000. Diploma Thesis, FU Berlin

    work page 2000

  6. [6]

    On the complexity of diagram testing.Order, 10(4):297–303, Dec 1993

    Graham Brightwell. On the complexity of diagram testing.Order, 10(4):297–303, Dec 1993

    work page 1993

  7. [7]

    Enumeration Algorithms for Real-World Networks: Efficiency and Beyond

    Alessio Conte. Enumeration Algorithms for Real-World Networks: Efficiency and Beyond. PhD thesis, Università di Pisa, 2018

    work page 2018

  8. [8]

    Efficient enumeration of graph orientations with sources.Discrete Appl

    Alessio Conte, Roberto Grossi, Andrea Marino, and Romeo Rizzi. Efficient enumeration of graph orientations with sources.Discrete Appl. Math., 246:22–37, 2018

    work page 2018

Show all 43 references
  1. [9]

    Springer International Publishing, 2016

    Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, and Luca Versari.Directing Road Networks by Listing Strong Orientations, pages 83–95. Springer International Publishing, 2016

    2016

  2. [10]

    A complexity theory for hard enumeration problems.Discrete Applied Mathematics, 268:191 – 209, 2019

    Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer. A complexity theory for hard enumeration problems.Discrete Applied Mathematics, 268:191 – 209, 2019

    2019

  3. [11]

    On Frank’s conjecture onk-connected orientations

    Olivier Durand de Gevigney. On Frank’s conjecture onk-connected orientations. Journal of Combinatorial Theory, Series B, 141:105 – 114, 2020

    2020

  4. [12]

    E. A. Dinits. Algorithm for solution of a problem of maximum flow in a network with power estimation. Sov. Math., Dokl., 11:1277–1280, 1970. 11

    1970

  5. [13]

    Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems.J. Assoc. Comput. Mach., 19:248–264, 1972

    1972

  6. [14]

    Loopless algorithms for generating permutations, combinations, and other com- binatorial configurations.J

    Gideon Ehrlich. Loopless algorithms for generating permutations, combinations, and other com- binatorial configurations.J. ACM, 20(3):500–513, 1973

    1973

  7. [15]

    Lattice structures from planar graphs.Electron

    Stefan Felsner. Lattice structures from planar graphs.Electron. J. Combin., 11(1), 2004. Research Paper 15

    2004

  8. [16]

    Rectangle and square representations of planar graphs

    Stefan Felsner. Rectangle and square representations of planar graphs. In Thirty essays on geometric graph theory, pages 213–248. Springer, New York, 2013

    2013

  9. [17]

    Pentagon contact representations

    Stefan Felsner, Hendrik Schrezenmaier, and Raphael Steiner. Pentagon contact representations. Electron. J. Combin., 25(3), 2018. Paper 3.39, 38

    2018

  10. [18]

    An algorithm for submodular functions on graphs.Ann

    András Frank. An algorithm for submodular functions on graphs.Ann. Discrete Math., 16:97–120, 1982

    1982

  11. [19]

    A note on k-strongly connected orientations of an undirected graph

    András Frank. A note on k-strongly connected orientations of an undirected graph. Discrete Math., 39(1):103–104, 1982

    1982

  12. [20]

    Harold N. Gabow. A framework for cost-scaling algorithms for submodular flow problems. In34th Annual Symposium on Foundations of Computer Science, Palo Alto, USA, November 1993, pages 449–458, 1993

    1993

  13. [21]

    Harold N. Gabow. Efficient splitting off algorithms for graphs. InProceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC ’94, pages 696–705, New York, NY, USA, 1994. ACM

    1994

  14. [22]

    Harold N. Gabow. Centroids, representations, and submodular flows.J. Algorithms, 18(3):586 – 628, 1995

    1995

  15. [23]

    Gilmer and Richard A

    Patrick M. Gilmer and Richard A. Litherland. The duality conjecture in formal knot theory. Osaka J. Math., 23(1):229–247, 1986

    1986

  16. [24]

    Gleiss, Josef Leydold, and Peter F

    Petra M. Gleiss, Josef Leydold, and Peter F. Stadler. Circuit bases of strongly connected digraphs. Discuss. Math., Graph Theory, 23(2):241–260, 2003

    2003

  17. [25]

    New York, NY: Springer, 2001

    Chris Godsil and Gordon Royle.Algebraic graph theory., volume 207. New York, NY: Springer, 2001

    2001

  18. [26]

    Triangle contact representations and duality.Discrete Comput

    Daniel Gonçalves, Benjamin Lévêque, and Alexandre Pinlou. Triangle contact representations and duality.Discrete Comput. Geom., 48(1):239–254, 2012

    2012

  19. [27]

    Efficient algorithms on distributive lattices

    Michel Habib, Raoul Medina, Lhouari Nourine, and George Steiner. Efficient algorithms on distributive lattices. Discrete Applied Mathematics, 110(2):169 – 187, 2001

    2001

  20. [28]

    Analgorithmforminimumcostarc-connectivityorientations

    SatoruIwataandYusukeKobayashi. Analgorithmforminimumcostarc-connectivityorientations. Algorithmica, 56(4):437–447, 2010

    2010

  21. [29]

    Morphisms, monoids and matrices

    Ulrich Knauer and Kolja Knauer.Algebraic graph theory. Morphisms, monoids and matrices. 2nd revised and extended edition., volume 41. Berlin: De Gruyter, 2nd revised and extended edition edition, 2019

    2019

  22. [30]

    A distributive lattice on the set of perfect matchings of a plane bipartite graph.Order, 20(1):13–29, 2003

    Peter Che Bor Lam and Heping Zhang. A distributive lattice on the set of perfect matchings of a plane bipartite graph.Order, 20(1):13–29, 2003

    2003

  23. [31]

    Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities

    Lap Chi Lau and Chun Kong Yung. Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities. SIAM J. Comput., 42(3):1185–1200, 2013

    2013

  24. [32]

    North-Holland, 1979

    László Lovász.Combinatorial Problems and Exercises. North-Holland, 1979. 12

    1979

  25. [33]

    Zur allgemeinen Kurventheorie.Fundamenta Mathematicae, 10(1):96–115, 1927

    Karl Menger. Zur allgemeinen Kurventheorie.Fundamenta Mathematicae, 10(1):96–115, 1927

    1927

  26. [34]

    John Alvah Nash-Williams

    Crispin St. John Alvah Nash-Williams. On orientations, connectivity and odd-vertex-pairings in finite graphs.Canadian Journal of Mathematics, 12:555–567, 1960

    1960

  27. [35]

    Vertex colourings in digraphs, Some Problems

    Victor Neumann-Lara. Vertex colourings in digraphs, Some Problems. Technical report, Waterloo, Canada, 1985

    1985

  28. [36]

    James B. Orlin. Max flows inO(nm) time, or better. In Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013, pages 765–

    2013

  29. [37]

    Lattice structure for orientations of graphs

    James Propp. Lattice structure for orientations of graphs. ArXiv: math/0209005, September 2002

    2002

  30. [38]

    Gray codes from antimatroids.Order, 10(3):239–252, 1993

    Gara Pruesse and Frank Ruskey. Gray codes from antimatroids.Order, 10(3):239–252, 1993

    1993

  31. [39]

    The lattice structure of the set of domino tilings of a polygon.Theoret

    Eric Rémila. The lattice structure of the set of domino tilings of a polygon.Theoret. Comput. Sci., 322(2):409–422, 2004

    2004

  32. [40]

    Matthew B. Squire. Generating the acyclic orientations of a graph.J. Algorithms, 26(2):275 – 290, 1998

    1998

  33. [41]

    SageMath, the Sage Mathematics Software System (Version 9.1)

    The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.1)

  34. [42]

    Strongly 2-connected orientations of graphs.Journal of Combinatorial The- ory, Series B, 110:67 – 78, 2015

    Carsten Thomassen. Strongly 2-connected orientations of graphs.Journal of Combinatorial The- ory, Series B, 110:67 – 78, 2015

    2015

  35. [43]

    Thurston

    William P. Thurston. Conway’s tiling groups.Amer. Math. Monthly, 97(8):757–773, 1990. 13

    1990

Pith tools

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