An Efficient Algorithm to Test Potentially Bipartiteness of Graphical Degree Sequences

Kai Wang

REVIEW 3 major objections 4 minor 18 references

An Efficient Algorithm to Test Potentially Bipartiteness of Graphical Degree Sequences

T0 review · 3 major / 4 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 A deterministic algorithm tests bipartite realizability of degree sequences in polynomial time, with a tunable, low one-sided error rate.

desk verdict A heuristic that could be useful, but the exactness claim is unproved and the error rates are self-referential. read the letter →

arxiv 1908.06821 v1 pith:YRHREWTN submitted 2019-08-19 math.CO cs.DS

Kai Wang This is my paper · ORCID

classification math.COcs.DS MSC 05C0705C8568Q2568W40

keywords graphicaldegreesequencebipartiterealizationpotentiallyGale-Rysertheorempolynomial-timealgorithmsubsetsumone-sidederror

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 addresses an open decision problem in graph theory: given a degree list $d$ that is known to be realizable by some simple graph, can we tell whether it is also realizable by a bipartite graph? The author presents a deterministic algorithm that is fast in practice and tunable in theory. It first applies seven quick necessary-condition tests that eliminate most non-bipartite sequences, then searches for a split of the degree sum into two equal halves and checks each split with the Gale–Ryser theorem. The search depth is controlled by a parameter $l_c$; when $l_c$ is a fixed polynomial in $n$, the whole algorithm runs in polynomial time and can only err by saying 'no' on some 'yes' instances. When $l_c$ is unlimited, the algorithm is exact but can take exponential time in the worst case.

What carries the argument

The central object is the candidate bipartition: a partition of the degree sequence into two subsequences $a$ and $b$ of equal sum, which any bipartite realization must induce. The Gale–Ryser condition—the conjugate of $a$ dominates $b$—is the exact feasibility test for such a split as a bipartite graph. The efficiency of the search comes from four structural restrictions: all degrees larger than $n-d_1$ must lie on the left side, the side's length must fall between greedy bounds $d_m$ and $l_1,l_2$, the index $x_0$ bounds the prefix of largest degrees to be considered, and the parameter $l_c$ limits how many combinations of small terms are enumerated, which is exactly where the polynomial-time/accuracy trade-off lives.

What would settle it

Run the algorithm with $l_c=n$ on all zero-free graphical degree sequences of lengths 24 and 25, and check every 'no' output against an independent feasibility test (for example, an exhaustive search over all splits of the degree sum, or an integer-programming feasibility check). Any sequence found by the independent test to be potentially bipartite but reported 'no' would falsify the claim that $l_c=n$ suffices at those lengths; if no such sequence appears, that aspect of the claim survives. A single explicitly constructed potentially bipartite sequence whose only successful splits are all skipped by every polynomial bound on $l_c$ would equally falsify the polynomial-time low-error claim.

Watch

Extended reading notes

Core claim

The central claim is that potential bipartiteness of a zero-free graphical degree sequence $d$ can be decided by combining the Gale–Ryser criterion with a heavily pruned enumeration of candidate splits, and that the enumeration can be cut short by a limit $l_c$ with only a very small chance of missing a valid split. On the paper's own terms: for every 'no' instance the algorithm always answers correctly, for 'yes' instances the seven rules plus the bounded enumeration either find a witness split or, with low empirical frequency, report 'no'; and with no bound on $l_c$ the answer is always correct. The paper further reports that the first-phase rules alone resolve a fraction of zero-free graphical sequences that approaches 1 as $n$ grows, and that with $l_c=n$ no errors were observed on all such sequences up to length 23.

Load-bearing premise

The load-bearing premise is that the enumeration phase is complete: for any degree sequence with a bipartite realization, the structured search over candidate splits will eventually reach a successful one when no limit is placed on $l_c$, and the reported low error rates treat the algorithm's own $l_c=n$ mode as ground truth rather than an independent decision procedure.

Editorial extensions

If this is right

With $l_c$ fixed to any polynomial in $n$, the algorithm decides every zero-free graphical degree sequence in polynomial time, and all its errors are false negatives on 'yes' instances.
The seven first-phase rules resolve a fraction of zero-free graphical degree sequences that the experiments show approaches 1 as $n$ grows, so most inputs are classified without entering the enumeration phase.
With $l_c=n$, the algorithm was exact on all zero-free sequences of length at most 23, and in the tested range up to $n=500$ no 'yes' instance was misclassified.
Every 'yes' answer comes with an explicit witness split $(a,b)$, so the algorithm doubles as a constructive search for a bipartite realization.

Reading between the lines

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

I infer that the empirical dominance of the seven rules, if provable, would make potential bipartiteness an increasingly rare property among zero-free graphical sequences, strengthening the case that the decision problem is easy on average even if its worst-case complexity stays open.
Because the error is one-sided, the algorithm can serve as a fast prescreen: a 'yes' is a certificate, while a 'no' can be rechecked with a larger $l_c$ or an exact method, yielding a practical two-tier procedure for large inputs.
The pattern of always putting large degrees on one side and filling with small degrees suggests that the hard 'yes' instances are those whose only successful splits require an unusual mix of mid-size degrees; quantifying that mix could yield a nontrivial upper bound on the minimal $l_c$ needed for exactness.

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.

Desk Editor's Note

read the letter

The thing to know: this is a deterministic, customizable heuristic for a long-open problem, but its two central claims — exactness with unlimited lc and very low error rates with lc=n — are not established. The first-phase rules are mostly standard necessary conditions (Mantel, subset-sum, Gale-Ryser); the new piece is the second-phase enumeration that restricts candidates to prefix-like subsets. The paper is honest that a small lc can miss yes instances and does not claim to resolve complexity.

Credit where earned: the seven rules are correctly motivated for the most part, and the empirical observation that the vast majority of zero-free graphical sequences are quickly rejected by those rules is interesting. The run-time data for n≤500 looks plausible, and the idea of making the search budget a parameter is reasonable for a heuristic.

Soft spots, in order of severity. First, the 'Without loss of generality' in Section 2 — that the subsequence dS can be chosen as the largest terms of {d1,…,dx0} — is not proved. For a fixed left side a, the algorithm only sees partitions whose intersection with that set is a prefix. If a successful partition needs a different subset, no exchange argument is provided, so the enumeration could skip all successful partitions even with unlimited lc. This is the same load-bearing gap the stress-test note flags. Second, the error rates in Table 2 are circular: B(n) is identified with the algorithm's own lc=n output, which is exactly the mode whose completeness is in question. Without an independent oracle for small n, the 'no error' claims are self-referential. Third, Rules 6 and 7 as rendered are suspect: residue and Murphy's bound are lower bounds on independence number, not clique number; used on the original sequence, Rule 6 would reject the star K_{1,3}, which is obviously bipartite. The notation for the complementary sequence is garbled in the text, so this may be a rendering issue, but as written it is a serious error.

Who this is for: a researcher in potentially P-graphic sequences might find the heuristic worth testing. A serious referee could ask for a completeness proof, an independent small-n oracle, and released code. As is, the exactness claim is unsupported. I would not desk-reject, because the problem is real and the gaps are fixable in principle; but this needs substantial revision before it can be trusted.

Referee Report

3 major / 4 minor

Summary. The paper proposes a deterministic algorithm for deciding whether a zero-free graphical degree sequence has a bipartite realization. The algorithm has a first phase of seven necessary conditions and a second, customizable enumeration phase that searches candidate bipartitions (a,b) under sum and length restrictions, with a parameter lc limiting the combinations of small terms tried. The authors claim that with lc bounded by a polynomial, the algorithm runs in polynomial time and has very low error on "yes" instances, and that with unlimited lc it always produces a correct output. Experiments on all zero-free graphical sequences up to n=23 indicate that the first phase resolves almost all inputs, and that setting lc=n yields no observed errors for n≤23.

Significance. If the correctness claims held, the paper would give a practical, customizable detection method for a long-standing open characterization problem of Rao, with the unusual feature of deterministic low-error heuristics. The first-phase necessary conditions (Rules 1–5) are simple and sound, the complexity analysis for fixed lc is transparent, and the exhaustive enumeration of all zero-free graphical degree sequences up to n=23 is a substantial computational accomplishment. However, the exactness claim rests on an unproved 'without loss of generality' in the enumeration phase, and the empirical error measurements are benchmarked against the algorithm's own exhaustive mode, which is the same mode whose completeness is in question. These issues make the central claims currently unsupported, though potentially repairable.

major comments (3)

[Section 2 (enumeration phase)] The restriction 'Without loss of generality, this subsequence dS can be chosen to be the largest terms of {d1,d2,...,dx0}' is load-bearing but unproved. For a fixed candidate left side a, the algorithm only constructs partitions whose intersection with the first x0 largest terms is a prefix (plus the mandatory af), yet a successful a need not have this property. Replacing a by another partition with a prefix intersection changes both the sum and the length ℓ(a), so it may violate the lower bounds in Restrictions 3 and 4 or the Gale-Ryser test; no exchange argument is supplied. Consequently, Section 3's assertion that with unlimited lc the algorithm 'will always produce a correct output' is not established by the manuscript.
[Section 4.1, Table 2] The ground truth B(n) used for the error rates is apparently the output of the algorithm itself in its lc=n mode, which is exactly the mode whose completeness is in question. The claim that lc=n makes no errors for n≤23 is therefore self-referential and does not provide independent evidence of correctness. The paper should describe how B(n) was obtained (e.g., by exhaustive enumeration of all bipartite graphs, or by an independent exact decision procedure), and if it was obtained with the same algorithm, the error-rate numbers should be reinterpreted accordingly.
[Section 2, Rules 6 and 7] Rule 6 as printed states that R(d) ≥ 3 implies non-bipartiteness, and its proof reasons from R(d) bounding the independence number to R(d) bounding the clique number. If R(d) denotes the residue of the original sequence, the rule is false: the degree sequence of K_{m,m} is potentially bipartite even though its residue is at least 3 for m ≥ 3. If the intended quantity is the residue of the complementary degree sequence d̄ (so that it bounds the clique number via the independence number of the complement), the notation and proof must state this explicitly. The same ambiguity applies to Rule 7 with Murphy's bound.

minor comments (4)

[Throughout] The symbol R(d) is used in the Introduction for the set of all non-isomorphic realizations and in Section 2 for the residue of a degree sequence; this overloaded notation should be disambiguated.
[Sections 2 and 3] The name 'Galy-Ryser' appears repeatedly; it should be 'Gale-Ryser'.
[Section 4.1] The paper does not provide the C++ source code or a precise description of how B(n) was computed, which limits reproducibility of the central error-rate tables; adding the code or a full algorithmic description would help.
[Section 5] The sentence 'Simply put, our algorithm is deterministic' is a truism; the point about deterministic versus randomized errors would be clearer if it distinguished fixed inputs from repeated runs.

Circularity Check

1 steps flagged · score 5.0 of 10

Empirical error rates are benchmarked against the algorithm's own exhaustive mode, making the lc=n no-error claim a self-consistency statement; the Section 3 exactness claim also rests on an unproved WLOG prefix restriction.

self definitional [Section 4.1, Table 2 and surrounding text]
"Let B(n) be the number of zero-free potentially bipartite graphical degree sequences of length n. ... The function values r(n) are obtained through a program that incorporates our decision algorithm into the algorithm to enumerate all degree sequences ... if we set lc = n, then our algorithm makes no error on all zero-free graphical degree sequences of length n ≤ 23."

B(n) is the ground-truth 'yes' set against which the error rates Bw(n)/B(n) are measured. The only counting program described in this section incorporates the paper's own decision algorithm; no independent decision procedure for potential bipartiteness is supplied. Thus B(n) is effectively the algorithm's own classification, and the statement that the lc=n mode 'makes no error' on B(n) is true by construction. The reported error rates therefore measure disagreement between lc=1 and lc=n outputs, not error relative to an external truth table; the empirical low-error prediction reduces to self-consistency.

full rationale

The seven rules and the Gale-Ryser check are self-contained applications of external theorems, so the core enumeration logic is not circular. The main circularity is limited to the empirical validation: the set B(n) of 'yes' instances used as ground truth is apparently produced by the same decision algorithm (the enumeration program 'incorporates our decision algorithm'), making the lc=n no-error claim a consistency statement rather than an independently verified error rate. Separately, Section 2's 'Without loss of generality, this subsequence dS can be chosen to be the largest terms of {d1,d2,...,dx0}' is unproved and load-bearing: it restricts the search to prefix intersections, and Section 3's assertion that unlimited lc always produces a correct output depends on it. I weigh that as an omitted-proof correctness risk, not as circularity, because no equation is reduced to its own input; it is a completeness gap. Because the paper's headline empirical quantity (very low error rate) is calibrated against the algorithm's own exhaustive mode, the circularity score is moderate rather than zero.

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

The central claim rests on standard theorems (Gale-Ryser, Mantel) and on known lower bounds from prior literature, which are reasonable. The critical unproven axiom is the completeness of the enumeration phase, and the experimental validation uses the algorithm itself as the ground truth.

free parameters (1)

lc = O(1) to O(n) in experiments
The limit on the number of small-term combinations enumerated in step (2). It controls the trade-off between polynomial runtime and the possibility of false negatives; the paper sets it to 1 or n in experiments.

assumptions (6)

standard math Gale-Ryser theorem: a bipartite graph with partite degree sequences a and b exists iff a' dominates b.
Used as the final condition in Section 2.
standard math Mantel's theorem: a bipartite graph on n vertices has at most n^2/4 edges.
Used in Rule 2.
domain assumption The residue R(d) of a degree sequence is a lower bound on the independence number of any realization.
Invoked in Rule 6 from Favaron et al., used to bound the clique number of the complement.
domain assumption Murphy's bound beta(d) is a lower bound on the independence number of any realization.
Invoked in Rule 7.
ad hoc to paper Completeness of the enumeration phase: every successful candidate bipartition will be generated when lc is unlimited.
Asserted in Section 3 without proof; the entire exactness claim depends on it.
domain assumption Input is restricted to zero-free graphical degree sequences.
The paper only considers sequences with all degrees positive.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An Efficient Algorithm to Test Potentially Bipartiteness of Graphical Degree Sequences." pith.science (2026). https://pith.science/paper/YRHREWTN

@misc{pith2026190806821,
  author       = {Pith},
  title        = {Pith review of: An Efficient Algorithm to Test Potentially Bipartiteness of Graphical Degree Sequences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YRHREWTN}},
  note         = {Machine review of arXiv:1908.06821}
}

read the original abstract

As a partial answer to a question of Rao, a deterministic and customizable efficient algorithm is presented to test whether an arbitrary graphical degree sequence has a bipartite realization. The algorithm can be configured to run in polynomial time, at the expense of possibly producing an erroneous output on some "yes" instances but with very low error rate.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Primes is in P

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. Primes is in P. Annals of Mathe- matics, 160(2):781–793, 2004

work page 2004
[2]

Recherches analytiques la th´ eorie des nom bres premiers

de la Vall´ ee Poussin. Recherches analytiques la th´ eorie des nom bres premiers. Ann. Soc. scient. Bruxelles , 20:183–256, 1896

work page
[3]

Chromatic number and complete graph substructures for degree sequences

Zdenˇ ek Dvoˇ r´ ak and Bojan Mohar. Chromatic number and complete graph substructures for degree sequences. Combinatorica, 33(5):513–529, 2013

work page 2013
[4]

Paul Erd˝ os and Robin J. Wilson. On the chromatic index of almost a ll graphs. Journal of Combinatorial Theory, Series B , 23(2):255–257, 1977

work page 1977
[5]

Favaron, M

O. Favaron, M. Mah´ eo, and J.-F. Sacl´ e. On the residue of a gr aph. Journal of Graph Theory, 15(1):39–64, 1991

work page 1991
[6]

D. Gale. A theorem on ﬂows in networks. Paciﬁc J. Math , 7(2):1073–1082, 1957

work page 1957
[7]

Garey and David S

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman & Co., New York, NY, USA, 1979. 10

work page 1979
[8]

Hadamard

J. Hadamard. Sur la distribution des z´ eros de la fonction zeta(s ) et ses cons´ equences arithm´ etiques.Bull. Soc. math. France , 24:199–220, 1896

work page

Show all 18 references

[9]

I. Holyer. The N P-completeness of edge-coloring. SIAM Journal on Computing , 10(4):718–720, 1981

1981
[10]

Faster pseudopolynomial tim e algorithms for subset sum

Konstantinos Koiliaris and Chao Xu. Faster pseudopolynomial tim e algorithms for subset sum. ACM Trans. Algorithms , 15(3):40:1–40:20, 2019

2019
[11]

W. Mantel. Problem 28 (solution by H. Gouwentak, W. Mantel, J. T eixeira de Mattes, F. Schuh and W. A. Wythoﬀ). Wiskundige Opgaven , 10:60–61, 1907

1907
[12]

Lower bounds on the stability number of graphs c omputed in terms of degrees

Owen Murphy. Lower bounds on the stability number of graphs c omputed in terms of degrees. Discrete Mathematics , 90(2):207–211, 1991

1991
[13]

Degree sequences and chromatic numbers of g raphs

Narong Punnim. Degree sequences and chromatic numbers of g raphs. Graphs and Combinatorics, 18(3):597–603, 2002

2002
[14]

S. B. Rao. A survey of the theory of potentially P-graphic and f orcibly P-graphic degree sequences. In Siddani Bhaskara Rao, editor, Combinatorics and Graph Theory: Lecture Notes in Mathematics, vol 885 , pages 417–440. Springer Berlin Heidelberg, 1981

1981
[15]

Alley CATs in search of good homes

Frank Ruskey, Robert Cohen, Peter Eades, and Aaron Scott . Alley CATs in search of good homes. In 25th S.E. Conference on Combinatorics, Graph Theory, and Co mputing, volume 102, pages 97–110. Congressus Numerantium, 1994

1994
[16]

H. J. Ryser. Combinatorial properties of matrices of zeros an d ones. Canadian Journal of Mathematics , 9:371–377, 1957

1957
[17]

Eﬃcient counting of degree sequences

Kai Wang. Eﬃcient counting of degree sequences. Discrete Mathematics , 342(3):888– 897, 2019

2019
[18]

A short constructive proof of A.R

Jian-Hua Yin. A short constructive proof of A.R. Rao’s charact erization of potentially kr+1-graphic sequences. Discrete Applied Mathematics , 160(3):352–354, 2012. 11

2012

Pith tools

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

[1] [1]

Primes is in P

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. Primes is in P. Annals of Mathe- matics, 160(2):781–793, 2004

work page 2004

[2] [2]

Recherches analytiques la th´ eorie des nom bres premiers

de la Vall´ ee Poussin. Recherches analytiques la th´ eorie des nom bres premiers. Ann. Soc. scient. Bruxelles , 20:183–256, 1896

work page

[3] [3]

Chromatic number and complete graph substructures for degree sequences

Zdenˇ ek Dvoˇ r´ ak and Bojan Mohar. Chromatic number and complete graph substructures for degree sequences. Combinatorica, 33(5):513–529, 2013

work page 2013

[4] [4]

Paul Erd˝ os and Robin J. Wilson. On the chromatic index of almost a ll graphs. Journal of Combinatorial Theory, Series B , 23(2):255–257, 1977

work page 1977

[5] [5]

Favaron, M

O. Favaron, M. Mah´ eo, and J.-F. Sacl´ e. On the residue of a gr aph. Journal of Graph Theory, 15(1):39–64, 1991

work page 1991

[6] [6]

D. Gale. A theorem on ﬂows in networks. Paciﬁc J. Math , 7(2):1073–1082, 1957

work page 1957

[7] [7]

Garey and David S

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman & Co., New York, NY, USA, 1979. 10

work page 1979

[8] [8]

Hadamard

J. Hadamard. Sur la distribution des z´ eros de la fonction zeta(s ) et ses cons´ equences arithm´ etiques.Bull. Soc. math. France , 24:199–220, 1896

work page