Optimization over Degree Sequences of Graphs

Gabriel Deza; Shmuel Onn

REVIEW 1 major objections 3 minor 12 references

Optimization over Degree Sequences of Graphs

T0 review · 1 major / 3 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 The paper proves that minimizing a sum of convex functions of vertex degrees over subgraphs of any given graph can be done in polynomial time via a minimum-cost perfect matching reduction.

desk verdict Solid convex-case algorithm with a matching reduction; the identical-functions NP-hardness claim is false as stated. read the letter →

arxiv 1908.09278 v1 pith:RTLMHNUH submitted 2019-08-25 math.OC cs.CCcs.DMcs.DSmath.CO

Gabriel Deza , Shmuel Onn This is my paper · ORCID

classification math.OCcs.CCcs.DMcs.DSmath.CO MSC 90C2705C0705C70

keywords degreesequencessubgraphoptimizationconvexfunctionsminimum-costperfectmatchingfactorproblem(lu)-factorexactdynamicprogramming

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 studies the problem of choosing a subgraph of a given graph to minimize the sum of per-vertex costs, where each vertex's cost depends only on its degree in the chosen subgraph. The authors prove that when every cost function is convex, this optimization problem is solvable in polynomial time for any graph, by encoding it as a minimum-cost perfect matching problem on an auxiliary graph of polynomial size. The result carries over to the classical $(l,u)$-factor problem, since interval degree constraints can be expressed with convex penalties. Conversely, the problem is NP-hard in general: already for bipartite graphs with convex costs on one side and concave on the other, deciding whether the optimal value is zero is NP-complete. The paper also gives polynomial-time algorithms for bipartite graphs with one side of fixed size and for graphs where all but a fixed number of cost functions are monotone.

What carries the argument

The auxiliary graph $L$ and its cost structure. For each vertex $i$ of $H$ and each $k=1,\dots,d_i(H)$, an edge $\{x_i^k,y_i^k\}$ in $L$ carries cost $c_i^k = f_i(k)-f_i(k-1)$; all other edges of $L$ have cost zero. Convexity of $f_i$ is exactly the condition $c_i^1 \le \cdots \le c_i^{d_i(H)}$, which forces any cheap perfect matching to use the lowest-index $x$-$y$ edges, making the matching's cost telescope to $\sum_i f_i(d_i(G)) - \sum_i f_i(0)$. A min-cost perfect matching in $L$ therefore encodes an optimal subgraph of $H$, turning a discrete optimization over subgraphs into a polynomially solvable matching problem.

What would settle it

The theorem implies the exact identity $c^* = f^* - \sum_{i=1}^n f_i(0)$ between the minimum perfect-matching cost in the auxiliary graph $L$ and the optimal subgraph objective. A concrete falsifier: on a small graph (say six vertices) with random convex integer functions, brute-force all subgraphs to find $f^*$, run the matching construction to get its extracted subgraph, and check whether the extracted subgraph is optimal; any mismatch disproves the theorem.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 1.2: for any graph $H$ on $n$ vertices and any convex integer-valued functions $f_1,\dots,f_n$, a subgraph $G\subseteq H$ minimizing $\sum_{i=1}^n f_i(d_i(G))$ can be found in polynomial time. The proof builds an auxiliary graph $L$ with $8|E|$ vertices and assigns to certain edges the marginal costs $c_i^k = f_i(k)-f_i(k-1)$. Convexity of each $f_i$ makes these marginals nondecreasing, so a minimum-cost perfect matching in $L$ selects exactly the edges of an optimal subgraph, and the matching cost equals the objective value shifted by the constants $f_i(0)$. The same construction solves the $(l,u)$-factor problem, and the exact matching problem is shown to be a special case of the degree-sequence problem.

Load-bearing premise

The main polynomial-time theorem assumes every vertex cost function is convex; if even one cost function is allowed to be nonconvex, the problem can become NP-hard, so convexity is the premise that carries the whole result.

Editorial extensions

If this is right

Convex-cost degree-sequence instances on arbitrary graphs are polynomial-time solvable, with no structural restrictions on the host graph.
The $(l,u)$-factor problem can be solved through the convex reduction, placing it in polynomial time by the same matching argument.
For bipartite graphs with one side of fixed size $r$, arbitrary cost functions are handled in polynomial time by a shortest-path dynamic program over the degrees of the small side.
When all but a fixed number of cost functions are either all nondecreasing or all nonincreasing, the problem is polynomial-time solvable for any graph.
Because the exact matching problem reduces to the degree-sequence problem, a polynomial algorithm for arbitrary functions on complete graphs would resolve the deterministic complexity of exact matching.

Reading between the lines

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

The matching reduction suggests a general template: separable convex costs whose marginals are ordered may often be solved by reduction to matching, pointing to a broader class of combinatorial optimization problems with this structure.
The fixed-side dynamic program has state count $O(n^{r+1})$; a natural testable extension is to benchmark the implementation on random bipartite instances to see how small $r$ must be for the method to be practical.
The hardness example in Proposition 1.1(1) may need a separate argument: with $f(0)=0$ the empty subgraph always attains value $0$, so the claimed equivalence to the cubic subgraph problem is not immediate as written.
The sharp contrast between the convex case (polynomial) and the convex-on-one-side/concave-on-the-other case (NP-hard) suggests the tractability boundary may lie exactly where marginal costs stop being globally ordered; testing intermediate monotonicity conditions could reveal additional tractable classes.

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

Deza-Onn gives a clean answer to a natural question: when each vertex has its own convex cost as a function of its degree, minimizing the total cost over subgraphs is polynomial-time solvable. The reduction to minimum-cost perfect matching is the sort of trick that makes you wonder why it wasn't obvious. Convexity makes the marginal costs nondecreasing, so assigning those marginals to the matching edges is sound, and the two inequalities in the proof genuinely pin down the optimum. I checked the construction; the auxiliary graph has polynomial size and the mapping is faithful.

The other algorithms are also new and sensible: the DP for unbalanced bipartite graphs with a fixed small side, and the reduction for mostly-monotone functions. These extend the earlier same-function result and are presented with enough detail to be reproducible. The reduction from exact matching in Section 2 is a nice observation and fits the paper's narrative.

Now the soft spot. Proposition 1.1(1) is wrong as stated. With f(0)=0, the empty subgraph always attains objective value 0, so "is the optimal value zero?" is trivially yes for every input. The intended reduction from the cubic subgraph problem would need B_i={3} and f(0)=1, not B_i={0,3} with f(0)=0. So the claimed NP-hardness for identical functions is not established by that argument. This flaw does not enter the proof of Theorem 1.2, and it does not affect Theorems 1.3, 1.4, or the bipartite convex-concave hardness in Proposition 1.1(2). It is a real mistake, but it is peripheral to the paper's main contribution.

I would bring this paper to a reading group and would cite Theorem 1.2 in future work on degree-sequence optimization. The paper deserves a serious referee; the right editorial outcome is a revise-and-resubmit that fixes Proposition 1.1(1) and, while at it, the small misstatement of the cubic subgraph problem.

Referee Report

1 major / 3 minor

Summary. The paper studies the problem of choosing a subgraph G of a given graph H on [n] to minimize the sum of given functions f_i evaluated at the degrees d_i(G). The main positive result, Theorem 1.2, claims that when all f_i are convex the problem is polynomial-time solvable for arbitrary H, by a reduction to minimum-cost perfect matching on an auxiliary graph L of size polynomial in n and |E(H)|. Theorem 1.3 gives a polynomial-time dynamic program for bipartite H with one side of fixed size r and arbitrary functions. Theorem 1.4 gives a polynomial-time algorithm when all but a fixed number of functions are simultaneously nondecreasing or nonincreasing. The paper also states an NP-hardness result for bipartite graphs with convex functions on one side and concave functions on the other, notes connections to general factor and (l,u)-factor problems, and gives a reduction of the exact matching problem to the degree-sequence optimization problem.

Significance. If the main claims stand, Theorem 1.2 is a clean and broadly applicable unification: every convex-cost degree-sequence optimization problem, including (l,u)-factor problems, is reduced to weighted perfect matching with no fitted parameters and with explicit polynomial bounds. The matching argument in the proof of Theorem 1.2 is coherent and self-contained, and the dynamic programs in Theorems 1.3 and 1.4 are transparent; Theorem 1.3 is accompanied by an implementation. The convex/concave bipartite hardness reduction and the exact matching connection are useful context. However, the identical-function hardness claim in Proposition 1.1(1) is false as stated, and this must be corrected before the paper can be accepted.

major comments (1)

[Section 2, Proposition 1.1(1)] Proposition 1.1(1) is false as written. With f(0)=0, the empty subgraph G=([n],∅) has objective value sum_i f_i(0)=0 for every graph H, so deciding whether the optimal value is zero is trivially yes for all instances. The proof's identification of the cubic subgraph problem with the factor problem B_i={0,3} is incorrect: a cubic subgraph requires each vertex to have degree exactly 3, so the correct factor sets are B_i={3}. With B_i={0,3}, the empty subgraph is always a factor and the NP-complete cubic subgraph problem is not encoded. The statement can be repaired by taking f(0)=1, f(3)=0, and f(i)=1 for all other i, so that a zero objective value is equivalent to a 3-regular spanning subgraph; alternatively the claim should be removed or weakened. This error is local and does not affect the proof of Theorem 1.2, but the published claim as it stands is mathematically incorrect.

minor comments (3)

[Section 4, proof of Theorem 1.3] The phrase "read oﬀ form it" should read "read off from it".
[References] In reference [2], "problmes" should be "problems", and in reference [6] the journal name should be "Matematikai Lapok".
[Section 3, Theorem 1.2 proof] The input model for the functions f_i is not explicitly stated; for complete clarity, the authors should state that each f_i is given by its values on {0,...,d_i(H)}, which is a list of length at most n+1 and hence a polynomial-size input.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity identified: Theorem 1.2 reduces to min-cost perfect matching by an explicit, parameter-free construction; the only notable flaw is a peripheral correctness error in Proposition 1.1(1), not a circular step.

full rationale

The central result (Theorem 1.2) is derived from first principles: the auxiliary graph L is constructed from H and the convex functions, and the equivalence c* = f* - sum f_i(0) is proven directly via the two inequalities labeled (1) and (2). The matching-to-subgraph direction uses the monotonicity of differences c^i_k <= c^i_{k+1}, which follows from convexity and is not an input assumption. No parameter is fitted, and no benchmark value is used to infer the output. Theorems 1.3 and 1.4 are equally self-contained: they reduce to shortest paths in explicitly constructed digraphs whose states enumerate possible degrees, with arc lengths exactly the given function values. The self-citations [4] and [11] are used only as background for prior works (identical convex functions over K_n, randomized exact matching) and are not load-bearing in any proof. The only substantive flaw is in Proposition 1.1(1), where the reduction from the cubic subgraph problem to the factor problem with B_i={0,3} is invalid because the empty subgraph always has value 0 with f(0)=0; this is a correctness error in a hardness remark, not a circular derivation, and it does not enter the proof of Theorem 1.2. Hence no circularity is present.

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

The paper introduces no fitted constants or invented entities. All proofs rely on standard polynomial-time subroutines (matching, shortest path) and on cited NP-completeness results from [3] and [8]. The application of the cubic-subgraph result in Proposition 1.1(1) is flawed, as noted.

assumptions (5)

standard math Minimum cost perfect matching is polynomial-time solvable on general graphs with integer edge weights.
Used in the proof of Theorem 1.2 to solve the degree sequence problem by reduction to matching; standard Edmonds algorithm.
standard math Convex integer functions have nondecreasing marginal differences c_k=f(k)-f(k-1).
Used in Theorem 1.2 to guarantee that the cheapest k edges among the x-y gadgets are the first k, making the matching cost equal the function value.
domain assumption The general factor problem is NP-complete for bipartite graphs of maximum degree 3 with B_i={1} on one side and B_i={0,3} on the other.
Cited from [3] and used in Proposition 1.1(2) to prove NP-hardness of the degree sequence problem with convex-concave functions.
domain assumption The cubic subgraph problem is NP-complete.
Cited from [8] and used in Proposition 1.1(1); the paper's translation to factor sets B_i={0,3} is invalid because the empty graph satisfies all constraints.
standard math Shortest paths in a directed acyclic graph can be found in linear time.
Used in Theorems 1.3 and 1.4 to solve the dynamic programming formulations.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimization over Degree Sequences of Graphs." pith.science (2026). https://pith.science/paper/RTLMHNUH

@misc{pith2026190809278,
  author       = {Pith},
  title        = {Pith review of: Optimization over Degree Sequences of Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RTLMHNUH}},
  note         = {Machine review of arXiv:1908.09278}
}

read the original abstract

We consider the problem of finding a subgraph of a given graph minimizing the sum of given functions at vertices evaluated at their subgraph degrees. While the problem is NP-hard already for bipartite graphs when the functions are convex on one side and concave on the other, we show that when all functions are convex, the problem can be solved in polynomial time for any graph. We also provide polynomial time solutions for bipartite graphs with one side fixed for arbitrary functions, and for arbitrary graphs when all but a fixed number of functions are either nondecreasing or nonincreasing. We note that the general factor problem and the (l,u)-factor problem over a graph are special cases of our problem, as well as the intriguing exact matching problem. The complexity of the problem remains widely open, particularly for arbitrary functions over complete graphs.

Figures

Figures reproduced from arXiv: 1908.09278 by the authors.

**Figure 1.** The graph L of Example 3.1 with blue costs and red minimum perfect cost matching 4 Unbalanced bipartite graphs Here we consider our problem over unbalanced bipartite graphs, with one side fixed and small. Theorem 1.3 For any fixed r, the optimization problem over degree sequences can be solved in polynomial time for any given bipartite graph H ⊆ Kr,n−r and any given functions f1, . . . , fn. Proof. Let H = (I, J, E)… view at source ↗

**Figure 2.** The digraph D of the dynamic program in Example 4.1 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** The digraph D of the dynamic program applied to H := K3,3 References [1] Billington, D.: Conditions for degree sequences to be realisable by 3-uniform hypergraphs. Journal of Combinatorial Mathematics and Combinatorial Computing 3:71–91 (1988) [2] Colbourn, C.J., W.L. Kocay, W.L., Stinson, D.R.: Some NP-complete problmes for hypergraph degree sequences. Discrete Applied Mathematics 14:239–254 (1986) [PITH_FULL_IMA… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Journal of Combinatorial Mathematics and Combinatorial Computing 3:71–91 (1988)

Billington, D.: Conditions for degree sequences to be realisable by 3-uniform hypergraphs. Journal of Combinatorial Mathematics and Combinatorial Computing 3:71–91 (1988)

work page 1988
[2]

Kocay, W.L., Stinson, D.R.: Some NP-complete problmes for hy- pergraph degree sequences

Colbourn, C.J., W.L. Kocay, W.L., Stinson, D.R.: Some NP-complete problmes for hy- pergraph degree sequences. Discrete Applied Mathematics 14:239–254 (1986) 9

work page 1986
[3]

Journal of Combinatorial Theory Series B 45:185–198 (1988)

Cornu´ ejols, G.: General factors of graphs. Journal of Combinatorial Theory Series B 45:185–198 (1988)

work page 1988
[4]

SIAM Journal on Discrete Mathematics 32:2067–2079 (2018)

Deza, A., Levin, A., Meesum, S.M., Onn, S.: Optimization over degree sequences. SIAM Journal on Discrete Mathematics 32:2067–2079 (2018)

work page 2018
[5]

Deza, G.: Implementation of the algorithm of Theorem 1.3 (2019), available online at: https://github.com/GabrielDeza/Degree-Sequence-Optimization

work page 2019
[6]

Matem- atikai Lopak 11:264–274 (1960)

Erd˝ os, P., Gallai, T.: Graphs with prescribed degrees of vertices (in Hungarian). Matem- atikai Lopak 11:264–274 (1960)

work page 1960
[7]

Combinatorics, Probability and Computing 22:366–383 (2013)

Erd˝ os, P., Kir´ aly, Z., Mikl´ os, I.: On the swap-distances of diﬀerent realizations of a graphical degree sequence. Combinatorics, Probability and Computing 22:366–383 (2013)

work page 2013
[8]

Freeman (1979)

Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman (1979)

work page 1979

Show all 12 references

[9]

Journal of Combinatorial Theory 8:391– 416 (1970)

Lov´ asz, L.: Subgraphs with prescribed valencies. Journal of Combinatorial Theory 8:391– 416 (1970)

1970
[10]

Combinatorica 7:105–113 (1987)

Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7:105–113 (1987)

1987
[11]

Zurich Lectures in Advanced Mathematics, European Mathematical Society (2010), available online at: http://ie.technion.ac.il/∼onn/Book/NDO.pdf

Onn, S.: Nonlinear Discrete Optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society (2010), available online at: http://ie.technion.ac.il/∼onn/Book/NDO.pdf

2010
[12]

Journal of Graph Theory 31:283–295 (1999)

Peled, U.N., Petreschi, R., Sterbini, A.: ( n,e )-graphs with maximum sum of squares of degrees. Journal of Graph Theory 31:283–295 (1999)

1999

Pith tools

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

[1] [1]

Journal of Combinatorial Mathematics and Combinatorial Computing 3:71–91 (1988)

Billington, D.: Conditions for degree sequences to be realisable by 3-uniform hypergraphs. Journal of Combinatorial Mathematics and Combinatorial Computing 3:71–91 (1988)

work page 1988

[2] [2]

Kocay, W.L., Stinson, D.R.: Some NP-complete problmes for hy- pergraph degree sequences

Colbourn, C.J., W.L. Kocay, W.L., Stinson, D.R.: Some NP-complete problmes for hy- pergraph degree sequences. Discrete Applied Mathematics 14:239–254 (1986) 9

work page 1986

[3] [3]

Journal of Combinatorial Theory Series B 45:185–198 (1988)

Cornu´ ejols, G.: General factors of graphs. Journal of Combinatorial Theory Series B 45:185–198 (1988)

work page 1988

[4] [4]

SIAM Journal on Discrete Mathematics 32:2067–2079 (2018)

Deza, A., Levin, A., Meesum, S.M., Onn, S.: Optimization over degree sequences. SIAM Journal on Discrete Mathematics 32:2067–2079 (2018)

work page 2018

[5] [5]

Deza, G.: Implementation of the algorithm of Theorem 1.3 (2019), available online at: https://github.com/GabrielDeza/Degree-Sequence-Optimization

work page 2019

[6] [6]

Matem- atikai Lopak 11:264–274 (1960)

Erd˝ os, P., Gallai, T.: Graphs with prescribed degrees of vertices (in Hungarian). Matem- atikai Lopak 11:264–274 (1960)

work page 1960

[7] [7]

Combinatorics, Probability and Computing 22:366–383 (2013)

Erd˝ os, P., Kir´ aly, Z., Mikl´ os, I.: On the swap-distances of diﬀerent realizations of a graphical degree sequence. Combinatorics, Probability and Computing 22:366–383 (2013)

work page 2013

[8] [8]

Freeman (1979)

Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman (1979)

work page 1979