{"id":"07dbb2e3-2b88-4f5b-8be6-c13b7b0016d6","arxiv_id":"1908.06821","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A polynomial-time customizable algorithm with empirically low error rates is proposed for testing potential bipartiteness of degree sequences, but without a proof of completeness.","lead":"A deterministic algorithm tests whether a graph degree sequence can be realized as a bipartite graph, using seven pruning rules and a customizable search. Configured with a limit, it runs in polynomial time but may misclassify a small fraction of 'yes' instances.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unlimited-lc exactness rests on an unproved WLOG in the enumeration phase; a successful bipartition whose selected prefix-subset is not the largest terms could be skipped, and error rates are benchmarked only against the algorithm's own exhaustive mode.","rationale":"The reader's conditional verdict is appropriate. The first-phase rules and necessary conditions are mostly straightforward; the real risk is in the second phase. The paper explicitly says 'Without loss of generality' at the dS step and asserts unlimited-lc correctness in Section 3, but neither is proved. Because the error-rate tables compare lc=1 against lc=n rather than against an independent decision procedure, the empirical low-error claim inherits the same unproved completeness. This is not a disagreement with consensus; it is a correctness risk in the central construction. A small-n exhaustive oracle plus a direct check of the prefix property would settle whether the WLOG is valid. If the check passes for all n≤14 and random larger cases, exactness remains unproved but the concern would be substantially weakened. No change to the conditional verdict is needed.","tokens_in":9406,"tokens_out":9462,"duration_ms":104415,"concrete_test":"Run an independent oracle on all zero-free graphical sequences with n≤14 (D(14)≈2.33M, feasible) and on random hard instances for n=20,30,50: for each sequence enumerate every subset a with sum |d|/2, enforce the paper's ℓ(a) bounds, and accept if any satisfies Gale-Ryser. Then run the paper's algorithm with lc unbounded and with lc=n and compare. Any yes instance rejected by unlimited mode disproves Section 3. To target the suspected gap directly, for each oracle-yes certificate record whether its intersection with the prefix {d1,...,dx0} is a prefix of that set; if a successful certificate exists whose intersection is not a prefix, and no exchange preserving sum and ℓ(a) yields one, the Section 2 WLOG is false. This settles whether the stated completeness claim holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Section 2's statement, after x0 is defined, that 'Without loss of generality, this subsequence dS can be chosen to be the largest terms of {d1,d2,...,dx0}.' This is the only place where the search is restricted beyond conditions that every successful bipartition must satisfy. For a fixed candidate left side a, the algorithm only reconstructs partitions whose intersection with {d1,...,dx0} is a prefix of that set (plus the mandatory af). If a successful a skips one of those large terms and compensates with smaller terms, the algorithm will not see that exact a. No exchange argument is supplied showing that such an a can be converted into another successful a whose intersection is a prefix; such an exchange changes both the sum (requiring removal of additional elements) and the length of a, which may violate the lower bounds on ℓ(a) and the Gale-Ryser domination test. Section 3's assertion that with unlimited lc 'our algorithm will always produce a correct output' therefore has no proof. The error-rate numbers in Table 2 are also not independent evidence: B(n) is apparently identified with the output of the algorithm itself in its lc=n mode, and that is exactly the mode whose completeness is in question.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9638,"tokens_out":8733,"duration_ms":84194,"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":[{"comment":"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":"Section 2 (enumeration phase)"},{"comment":"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":"Section 4.1, Table 2"},{"comment":"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.","section":"Section 2, Rules 6 and 7"}],"minor_comments":[{"comment":"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.","section":"Throughout"},{"comment":"The name 'Galy-Ryser' appears repeatedly; it should be 'Gale-Ryser'.","section":"Sections 2 and 3"},{"comment":"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":"Section 4.1"},{"comment":"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.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The main correctness risk is the unproved 'without loss of generality' in the enumeration phase. If that cannot be repaired, the paper should be recast as a heuristic with error rates measured against an independent exact oracle, rather than claiming exactness for unlimited lc. The benchmarking circularity in Table 2 should be addressed in revision; an independent brute-force check for small n would strengthen the empirical claims considerably."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nCredit 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.\n\nSoft 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.\n\nWho 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.","headline":"A heuristic that could be useful, but the exactness claim is unproved and the error rates are self-referential.","tokens_in":10105,"tokens_out":10593,"would_cite":false,"duration_ms":98765,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C07","05C85","68Q25","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A deterministic algorithm tests bipartite realizability of degree sequences in polynomial time, with a tunable, low one-sided error rate.","keywords":["graphical degree sequence","bipartite realization","potentially bipartite","Gale-Ryser theorem","polynomial-time algorithm","subset sum","one-sided error"],"falsifier":"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.","tokens_in":9167,"feed_emoji":"🧮","tokens_out":11750,"duration_ms":100884,"temperature":0.7,"pith_summary":"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.","feed_headline":"Polynomial-time algorithm tests bipartite degree sequences","feed_subtitle":"The deterministic search rarely misses a yes-instance and never marks a no-instance yes.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Gale–Ryser theorem used to test each candidate bipartition.","marker":"[6]"},{"why":"Provides the conjugate-dominance criterion that the Gale–Ryser test applies.","marker":"[16]"},{"why":"Gives the edge bound for bipartite graphs used in Rule 2.","marker":"[11]"},{"why":"Introduces the residue parameter used by Rule 6 as an independence-number lower bound.","marker":"[5]"},{"why":"Introduces the stability-number lower bound used by Rule 7.","marker":"[12]"},{"why":"Cites the subset-sum problem's NP-completeness, motivating the dynamic-programming step for finding candidate bipartitions.","marker":"[7]"},{"why":"Provides the pseudopolynomial-time subset-sum algorithm used for Rule 1.","marker":"[10]"},{"why":"Supplies the degree-sequence enumeration used to generate the experimental tables.","marker":"[15]"},{"why":"States the open problem of characterizing potentially bipartite graphical degree sequences that this paper addresses.","marker":"[14]"}],"fun_headline_variants":["Almost always correct bipartite test for degree sequences","Bipartite degree sequence test: fast, rarely wrong","Almost-sure bipartite test for graphical sequences","Bipartite check for degree sequences: quick, rarely errs","Test bipartite degree sequences with tiny error rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Almost always correct bipartite test for degree sequences","Bipartite degree sequence test: fast, rarely wrong","Almost-sure bipartite test for graphical sequences","Bipartite check for degree sequences: quick, rarely errs","Test bipartite degree sequences with tiny error rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000657,"raw_usage":{"total_tokens":2908,"prompt_tokens":748,"completion_tokens":2160,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":364,"completion_tokens_details":{"reasoning_tokens":2097}},"tokens_in":364,"tokens_out":2160,"duration_ms":15406,"temperature":1.0,"reasoning_tokens":2097,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:34:51.651640+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Gale–Ryser theorem used to test each candidate bipartition."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the conjugate-dominance criterion that the Gale–Ryser test applies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the edge bound for bipartite graphs used in Rule 2."},{"cited_title":"Favaron, M","cited_arxiv_id":null,"evidence_quote":"Introduces the residue parameter used by Rule 6 as an independence-number lower bound."},{"cited_title":"Lower bounds on the stability number of graphs c omputed in terms of degrees","cited_arxiv_id":null,"evidence_quote":"Introduces the stability-number lower bound used by Rule 7."},{"cited_title":"Garey and David S","cited_arxiv_id":null,"evidence_quote":"Cites the subset-sum problem's NP-completeness, motivating the dynamic-programming step for finding candidate bipartitions."},{"cited_title":"Faster pseudopolynomial tim e algorithms for subset sum","cited_arxiv_id":null,"evidence_quote":"Provides the pseudopolynomial-time subset-sum algorithm used for Rule 1."},{"cited_title":"Alley CATs in search of good homes","cited_arxiv_id":null,"evidence_quote":"Supplies the degree-sequence enumeration used to generate the experimental tables."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the open problem of characterizing potentially bipartite graphical degree sequences that this paper addresses."}],"review_version":1}