{"id":"8137dee7-f2e4-43a1-b36f-3946dc7426d7","arxiv_id":"1908.09278","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Optimization over degree sequences is polynomial-time solvable when all vertex cost functions are convex on any graph, and in several unbalanced or monotone structured cases, while remaining NP-hard in general.","lead":"This paper studies choosing a subgraph of a given graph to minimize the total cost of the vertex degrees, where each vertex has its own cost function. It proves several cases are solvable in polynomial time, including all convex cost functions on any graph, and connects the problem to matching and factor problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection to Theorem 1.2 identified; the Proposition 1.1(1) flaw noted by the reader is valid but peripheral.","rationale":"The reader's weakest_assumption correctly identifies a false statement in Proposition 1.1(1), but that statement is not load-bearing for the strongest claim, Theorem 1.2. I checked the two inequalities (1) and (2) in Section 3 in detail. The forward direction constructs a valid perfect matching by pairing leftover u/v vertices with x/y vertices, and the reverse direction correctly infers that the x-y matched pairs K_i have size d_i(G), so the cost lower bound follows from the nondecreasing convex differences. No hidden assumption or circularity appears in the convex-case argument. The proof is constructive and parameter-free, which is strong independent support even without machine-checked verification. The cited implementation covers Theorem 1.3 rather than Theorem 1.2, so a small brute-force cross-check is still worth running. Since no new load-bearing concern about the central claim was identified, the reader's conditional verdict should remain unchanged.","tokens_in":7035,"tokens_out":13165,"duration_ms":138839,"concrete_test":"Implement the Theorem 1.2 gadget for every simple graph H on n<=6 and random convex integer functions f_i on {0,...,d_i(H)}, solve the resulting minimum-cost perfect matching with a standard blossom implementation, and compare against brute-force enumeration of all subgraphs of H. If any instance disagrees, the matching reduction has a hidden flaw; otherwise the central convex-case claim is confirmed on this exhaustive test set.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified to the central claim, Theorem 1.2. The reduction to minimum-cost perfect matching is internally sound: every subgraph G maps to a perfect matching of cost sum_i(f_i(d_i(G))-f_i(0)), and every matching read off the u-side gives a subgraph G' whose matching cost is at least sum_i(f_i(d_i(G'))-f_i(0)), using the nondecreasing differences of each convex f_i. Equality therefore forces optimality, and the auxiliary graph L has polynomial size in n and |E(H)|. The one substantive error in the manuscript is Proposition 1.1(1), exactly as the reader states: with f(0)=0, the empty subgraph already attains objective value 0, so deciding whether the optimum is zero is trivially yes, and the claimed NP-hardness for identical functions is not established. This error does not enter the proof of Theorem 1.2 and does not affect the convex-case algorithm or the convex-concave bipartite hardness statement in Proposition 1.1(2).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7220,"tokens_out":9203,"duration_ms":93208,"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":[{"comment":"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.","section":"Section 2, Proposition 1.1(1)"}],"minor_comments":[{"comment":"The phrase \"read off form it\" should read \"read off from it\".","section":"Section 4, proof of Theorem 1.3"},{"comment":"In reference [2], \"problmes\" should be \"problems\", and in reference [6] the journal name should be \"Matematikai Lapok\".","section":"References"},{"comment":"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.","section":"Section 3, Theorem 1.2 proof"}],"recommendation":"major_revision","confidential_remarks":"The central convex-case result appears sound and the paper makes a valuable contribution, but the false Proposition 1.1(1) is a substantive error that must be fixed. The fix is straightforward and does not touch the main theorem, so I would not reject the paper if the authors correct the hardness statement and any associated text."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nNow 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.\n\nI 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.","headline":"Solid convex-case algorithm with a matching reduction; the identical-functions NP-hardness claim is false as stated.","tokens_in":7721,"tokens_out":3181,"would_cite":true,"duration_ms":30832,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","05C07","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["degree sequences","subgraph optimization","convex functions","minimum-cost perfect matching","factor problem","(l,u)-factor","exact matching","dynamic programming"],"falsifier":"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.","tokens_in":6830,"feed_emoji":"🧮","tokens_out":11913,"duration_ms":108977,"temperature":0.7,"pith_summary":"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.","feed_headline":"Convex degree-sequence optimization is polynomial-time for every graph","feed_subtitle":"Any convex sum of vertex-degree costs reduces to one minimum-cost perfect matching.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes the same-function complete-graph case and the NP-completeness of hypergraph degree-sequence realization, the prior result that Theorem 1.2 generalizes.","marker":"[4]"},{"why":"Provides the NP-hardness of general factors on bipartite max-degree-3 graphs used in Proposition 1.1(2).","marker":"[3]"},{"why":"Introduces the (l,u)-factor problem, shown here to be a convex special case of the degree-sequence problem.","marker":"[9]"},{"why":"Supplies the NP-complete cubic subgraph problem cited in the hardness reduction.","marker":"[8]"},{"why":"Gives the randomized algorithm for exact matching that the paper contrasts with open deterministic complexity.","marker":"[10]"},{"why":"Earlier result for the complete graph with identical convex functions, the seed case extended by Theorem 1.2.","marker":"[12]"}],"fun_headline_variants":["Convex degree costs reduce to perfect matching, poly-time for all graphs","Minimize convex degree sums in P for every graph","All convex vertex-degree costs minimized in polynomial time","Poly-time solution for convex degree-sequence optimization","Convex degree-sequence problem falls into P for all graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Convex degree costs reduce to perfect matching, poly-time for all graphs","Minimize convex degree sums in P for every graph","All convex vertex-degree costs minimized in polynomial time","Poly-time solution for convex degree-sequence optimization","Convex degree-sequence problem falls into P for all graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001561,"raw_usage":{"total_tokens":6192,"prompt_tokens":856,"completion_tokens":5336,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":472,"completion_tokens_details":{"reasoning_tokens":5258}},"tokens_in":472,"tokens_out":5336,"duration_ms":38793,"temperature":1.0,"reasoning_tokens":5258,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:17:54.452356+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"SIAM Journal on Discrete Mathematics 32:2067–2079 (2018)","cited_arxiv_id":null,"evidence_quote":"Establishes the same-function complete-graph case and the NP-completeness of hypergraph degree-sequence realization, the prior result that Theorem 1.2 generalizes."},{"cited_title":"Journal of Combinatorial Theory Series B 45:185–198 (1988)","cited_arxiv_id":null,"evidence_quote":"Provides the NP-hardness of general factors on bipartite max-degree-3 graphs used in Proposition 1.1(2)."},{"cited_title":"Journal of Combinatorial Theory 8:391– 416 (1970)","cited_arxiv_id":null,"evidence_quote":"Introduces the (l,u)-factor problem, shown here to be a convex special case of the degree-sequence problem."},{"cited_title":"Freeman (1979)","cited_arxiv_id":null,"evidence_quote":"Supplies the NP-complete cubic subgraph problem cited in the hardness reduction."},{"cited_title":"Combinatorica 7:105–113 (1987)","cited_arxiv_id":null,"evidence_quote":"Gives the randomized algorithm for exact matching that the paper contrasts with open deterministic complexity."},{"cited_title":"Journal of Graph Theory 31:283–295 (1999)","cited_arxiv_id":null,"evidence_quote":"Earlier result for the complete graph with identical convex functions, the seed case extended by Theorem 1.2."}],"review_version":1}