{"id":"77bf4c38-c350-4c11-be49-35f49d8c19f2","arxiv_id":"2512.08554","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Induced tree and path polytopes of chordal graphs admit compact extended formulations and both families of incidence vectors form Hilbert bases.","lead":"This paper gives explicit linear-programming descriptions (extended formulations) for the convex hulls of induced trees and induced paths in chordal graphs. If correct, it also implies these polytopes have the integer decomposition property and that weighted variants of both optimization problems are polynomial-time solvable.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Path Hilbert-basis proof hinges on Claim 2.2, whose contraction step assumes a connected vertex set without proof; a counterexample here would invalidate Theorems 2.11–2.13.","rationale":"The central claim of the paper is that the induced tree/path extended incidence vectors of chordal graphs form Hilbert bases, which yields the polytope equalities. The tree version (Thm 1.1) is a self-contained induction that does not depend on Claim 2.2; I found no gap there beyond cosmetic typos. The path version (Thm 2.11) is structurally much more delicate and explicitly invokes Claim 2.2 in Lemmas 2.7 and 2.10 and in the iterative K_Ψ construction. Therefore the path Hilbert-basis proof is the load-bearing part of the central claim. Claim 2.2's proof is not fully rigorous: contracting an edge set to a single vertex requires the edge set to be connected, and the manuscript does not prove this. If the claim fails for some chordal graph, the reorganization step in Theorem 2.11 cannot be justified, and the consequences (Thm 2.13, Corollaries 2.14, 2.17) would need re-evaluation. The concrete enumeration test I propose would settle whether Claim 2.2 itself is true; if it passes, the proof can likely be repaired, but as written the gap warrants the reader's CONDITIONAL verdict. I therefore agree with the reader's weakest assumption and recommend no change to the verdict: CONDITIONAL remains appropriate until the contraction argument is made rigorous or a counterexample is found.","tokens_in":15757,"tokens_out":32067,"duration_ms":253904,"concrete_test":"Use exhaustive enumeration: for every chordal graph on at most 8 vertices (generate all graphs, test chordality via perfect elimination ordering), enumerate all induced paths P1,P2 sharing an extremity u with distinct neighbors u1,u2. For each pair check whether u1u2∈E(G) or V(P1)∪V(P2) induces a path. If a counterexample exists, Claim 2.2 is false and Theorem 2.11 requires major revision; if none exists, the statement is supported, and the remaining task is to make the contraction proof rigorous by proving the contracted edge set is connected (or by handling disconnected cases separately).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Claim 2.2 (used in Lemmas 2.7, 2.10 and in the K_Ψ reorganization of Theorem 2.11) asserts that for two induced paths P1,P2 of a chordal graph sharing extremity u with distinct neighbors u1,u2, either u1u2 is an edge or P1∪P2 is an induced path. Its proof says 'Let us contract all the edges in E(P1∪P2\\{u1,u2,u}) to a single vertex w.' This contraction to a single vertex is only defined if that vertex set induces a connected subgraph. The proof does not establish connectivity. It can fail: if P1 and P2 share u and u1 (with u1 interior in P2) and have no further intersection or cross edge, the set {P1,P2}\\{u,u1,u2} can split into two components (e.g., P1 = u-u1-a, P2 = u-u2-b-u1-c). In that situation the contracted graph is not a single C4, and the chordality contradiction does not follow. The later reorganization argument in Theorem 2.11 iteratively applies Claim 2.2 to merge paths; if Claim 2.2 admits a chordal counterexample, the Hilbert-basis theorem (and with it Theorems 2.13, Corollaries 2.14 and 2.17) collapses. The manuscript contains no proof of the missing connectivity assertion, and the reader's flag is accurate. The tree-side proof (Thm 1.1) does not rest on Claim 2.2 and appears internally sound; the typos in Thm 1.3 (wrong vertex set) and Thm 2.15 (rank off by one) are repairable and not the decisive risk.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines extended incidence vectors for induced trees and induced paths of a graph, together with cones C_T(G) and C_P(G). It claims that for chordal graphs these incidence vectors form Hilbert bases (Theorems 1.1 and 2.11), and that intersecting the cones with x(V)-y(E)=1 yields binary polytopes T(G) and P(G), so that chordality is equivalent to integrality (Theorems 1.3 and 2.13). It also characterizes the facet-defining inequalities among those of C_P(G) (Theorem 2.15), proves a quadratic bound on the non-dominated such inequalities (Theorem 2.16), and concludes polynomial-time solvability for maximum-weight induced tree and induced path on chordal graphs.","tokens_in":16160,"tokens_out":27576,"duration_ms":237553,"significance":"If the Hilbert-basis results are correct, the paper gives a compact extended formulation for the induced tree polytope and an exponential—but polynomially enumerable—extended formulation for the induced path polytope of chordal graphs, with the integer decomposition property as a byproduct. The tree-side proof (Theorem 1.1) is self-contained and plausible, and the cone C_T is defined independently of the claimed generating set, so this part is a genuine contribution. The path-side proof, however, rests on Claim 2.2, whose proof is incomplete, and the facet characterization in Theorem 2.15 appears to be false as stated. These issues undermine two of the main advertised contributions.","major_comments":[{"comment":"The proof contracts all edges in E(P1∪P2\\{u1,u2,u}) to a single vertex w. Such a contraction collapses the set S = V(P1∪P2)\\{{u,u1,u2}} only if G[S] is connected. The manuscript does not prove connectivity, and it is not a formal consequence of the preceding sentences. For example, if P1 = u-u1-a and P2 = u-u2-b-u1-c, then S = {a,b,c} has no edges among its vertices (this particular graph is not chordal, but it shows the missing argument is nontrivial). Since Claim 2.2 is invoked in Lemmas 2.7 and 2.10 and in the K_Ψ reorganization step of Theorem 2.11, the Hilbert-basis proof for induced paths is incomplete as written. The author needs either to prove that G[S] is connected under the chordal hypotheses or to replace the contraction with a different argument before Theorem 2.11 can be accepted.","section":"§2.1, Claim 2.2"},{"comment":"The characterization is false as stated. Take G = K5, let w=1 and K={2}. Then C(K∪{w}) = {3,4,5}, and G[C(K∪{w})] = K3, which has no bipartite connected component, so the stated condition holds. Inequality (5) is 2y_{12} + y_{13} + y_{14} + y_{15} ≤ 2x_1. The extreme points of P(G) for K5 are the 5 singletons and 10 edges. Those satisfying equality are the four singletons not containing 1, the six edges among {2,3,4,5}, and the edge {1,2}, for a total of 11 vertices. Since P(G) has dimension 14 (its affine hull is exactly x(V)-y(E)=1), a facet requires 14 affinely independent vertices; a face with only 11 vertices cannot be a facet. Thus the 'if' direction of Theorem 2.15 is contradicted by a chordal graph.","section":"§2.2, Theorem 2.15"},{"comment":"Even setting aside the K5 counterexample, the construction of the remaining tight points is invalid. The proof matches each edge uw ∈ δ(w, C(K∪{w})) to an edge uv ∈ T ⊆ E(G[C(K∪{w})]). But then u and v are adjacent in G, so the set {u,w,v} induces a triangle, not an induced path. The text asserts that u and v are non-adjacent, which contradicts the choice of uv as an edge of T. The proof therefore does not produce the required |δ(w,C(K∪{w}))| additional tight extreme points. The statement may need to be reformulated using the complement of G[C(K∪{w})], but as written both the statement and the proof are incorrect.","section":"§2.2, Theorem 2.15 proof, 'if' direction"},{"comment":"The domination argument also contains a gap. The proof asserts that K_j = (∪_{i=1}^ℓ S^j_i) ∪ K ∪ {w} is a clique, where S^j_i are the two stable sets of a bipartite component G_i of G[C(K∪{w})]. However, S^j_i is a stable set, so its elements are pairwise nonadjacent, and vertices from different connected components are nonadjacent by definition of components. Hence the union is generally not a clique. This invalidates the claimed domination of the inequality by two other inequalities and further indicates that the facet analysis in Theorem 2.15 needs substantial revision.","section":"§2.2, Theorem 2.15 proof, 'only if' direction"}],"minor_comments":[{"comment":"In the notation section, 'G\\uv¨' appears to be a typo for 'G\\uv'.","section":"Definitions"},{"comment":"In the induction step, 'nonnegative integer combination of induced paths’ extended incidence vectors' should read 'induced trees’ extended incidence vectors'.","section":"Proof of Theorem 1.1"},{"comment":"The caption refers to 'the proof of Theorem 1.3', but the figure is used in the proof of Theorem 1.1.","section":"Figure 1 caption"},{"comment":"Conjecture 2.4 is immediately proved as Theorem 2.11 in the same section. It would be clearer to present it as a statement or proposition, not a conjecture.","section":"Conjecture 2.4 / Theorem 2.11"},{"comment":"The proof says the whole matrix has rank |V|+|E|, but only |V|+|E|-1 rows are constructed. The correct target rank is |V|+|E|-1, matching the dimension of the polytope.","section":"Proof of Theorem 2.15"},{"comment":"Minor typos include 'initilization' for 'initialization' and several missing or duplicated words.","section":"Section 2.2"}],"recommendation":"major_revision","confidential_remarks":"The tree half of the paper appears sound and could be a publishable contribution on its own. The path half, however, is not ready: Claim 2.2 is load-bearing and its proof has a real gap, and Theorem 2.15 is contradicted by a simple chordal example (K5). The Hilbert-basis claim for paths may still be true, but the manuscript does not currently establish it, and the facet analysis needs to be reconsidered from the ground up. I would suggest the editor request a major revision with a careful reworking of the path section."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The result is real: this is the first compact extended formulation for induced tree and path polytopes on chordal graphs, and the Hilbert-basis / IDP part is the core. The proofs are constructive and the cone descriptions are natural. I gave the long path proof a close read; the reorganization argument in Theorem 2.11 is intricate but I believe it holds. The facet characterization and the O(|V|^2) bound on non-dominated inequalities are nice contributions.\n\nThe soft spots are mostly presentation. Theorem 1.3 writes the non-chordal point with x_w=1 on all of V\\v; that makes the hyperplane count fail unless the hole spans all vertices. It should be the hole vertices only. At the end of Theorem 2.15 the rank is given as |V|+|E| but the dimension is |V|+|E|-1; the count is off by one. Some implicit assumptions need stating: every vertex can be last in a PEO (they cite Dirac, fine), and the contraction in Claim 2.2 assumes the vertex set P1∪P2 minus {u,u1,u2} is connected. That connectivity is not explicitly justified, but I don't think it's a real gap. The stress-test counterexample does not survive: in their example P2 has u and u1 nonconsecutive while the edge u-u1 exists in G because P1 contains it, so P2 is not induced; and the graph is not chordal. If the union of two induced paths sharing an endpoint fails to be a path, you get a cycle containing u,u1,u2, and the rest of the cycle plus any branches attaches to vertices of that cycle other than u1,u2, so the contracted set is connected. The proof of Claim 2.2 should spell this out, but the claim stands.\n\nThe tree-side proof is sound and doesn't depend on Claim 2.2. The paper is honest about the exponential path system and the redundant inequalities in the polynomial superset. I found no fit-to-conclusion problem; the cones are defined independently and the Hilbert-basis proofs actually generate them.\n\nWho is this for? Polyhedral combinatorics people, especially those working on structured graph polytopes and IDP. It deserves a serious referee, and it should be publishable after revision. I'd bring it to a reading group and I'd cite it.","headline":"Solid new Hilbert-basis results for induced tree/path polytopes in chordal graphs; proofs essentially correct, but the write-up has a few typos and one terse contraction step that needs a clearer justification.","tokens_in":16640,"tokens_out":14334,"would_cite":true,"duration_ms":119850,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","05C75","52B12"],"pacs":[],"model":"deepseek-v4-flash","headline":"For chordal graphs, this paper proves that the extended incidence vectors of induced trees and of induced paths form Hilbert bases, so both polytopes have compact extended formulations and weighted optimization is polynomial-time.","keywords":["induced trees","induced paths","chordal graphs","Hilbert basis","extended formulations","integer decomposition property","polyhedral combinatorics","polytopes"],"falsifier":"The theorems predict that for any chordal graph the polytope T(G) or P(G) has only binary extreme points and that every integer point of the cone is an integer conic combination of incidence vectors. A single counterexample to either statement — found by brute-force enumeration on small chordal graphs, or a non-chordal graph for which T(G) or P(G) is nonetheless binary — would refute the characterization. A more surgical check: search for two induced paths in a chordal graph sharing an endpoint whose second vertices are nonadjacent and whose union is not an induced path; such a pair would viol","tokens_in":15632,"feed_emoji":"🌳","tokens_out":8481,"duration_ms":70769,"temperature":0.7,"pith_summary":"This paper asks when the convex hulls of induced trees and induced paths admit simple, small linear descriptions. The answer it proves: in a chordal graph, the cone generated by the extended incidence vectors (vertices plus edges) of induced trees, and likewise of induced paths, is generated by those incidence vectors as a Hilbert basis — every integer point of the cone is a nonnegative integer combination of them. Cutting that cone with the single hyperplane x(V)-y(E)=1 then yields the induced tree polytope and the induced path polytope exactly, and the paper shows this description is exact precisely for chordal graphs. The consequences are algorithmic: both polytopes have the integer decomposition property, the induced-path formulation collapses to O(|V|^2) non-dominated inequalities, and weighted maximum induced tree and induced path problems become polynomial-time solvable on chordal graphs.","feed_headline":"One hyperplane pins down tree/path polytopes on chordal graphs","feed_subtitle":"The result makes weighted induced-tree and induced-path optimization polynomial-time on chordal graphs.","key_machinery":"The load-bearing objects are the extended incidence vectors ξ_W = (χ_W, ζ_E(W)), which encode an induced tree or path by both its vertices and its edges, and the Hilbert-basis property: every integer point of the cone C_T(G) or C_P(G) is a nonnegative integer combination of such vectors. The cone descriptions matter. C_T(G) uses one inequality per vertex and incident maximal clique, enforcing that an induced tree never has two edges from the same vertex into one triangle; C_P(G) uses inequalities (5) that count edges incident to a vertex against a clique K in its neighborhood, with edges to C(K∪{w}) counted once and edges to K counted twice. The proofs proceed by induction on a simplicial ve","core_discovery":"The central claim is a Hilbert-basis theorem for chordal graphs. For the induced tree cone C_T(G), defined by inequalities that forbid a vertex from sending two edges into any triangle of a maximal clique, the extended incidence vectors of induced trees form a Hilbert basis (Theorem 1.1); the identical statement holds for the induced path cone C_P(G), defined by inequalities (5) that bound weighted sums of edges incident to each vertex, with the path incidence vectors forming a Hilbert basis (Theorem 2.11). In both cases, intersecting the cone with the hyperplane x(V)-y(E)=1 gives a polytope whose binary points are exactly the incidence vectors of induced trees or induced paths. The paper pr","pith_inferences":["The Hilbert-basis route likely extends beyond chordal graphs: the paper notes C4 already satisfies it, so the exact class of graphs with Hilbert bases is larger and may have a forbidden-induced-subgraph characterization; a natural next step is to identify it.","The facet characterization of inequalities (5) suggests a polynomial-time separation routine for the compact path formulation, which the paper does not spell out but which would make the extended formulation directly usable in cutting-plane solvers.","The same recipe — prove a Hilbert basis for the cone of incidence vectors of a hereditary family, then cut with x(V)-y(E)=1 — could yield compact extended formulations for other induced subgraph polytopes, such as induced forests, on graph classes with a similar elimination structure.","Because T(G) and P(G) are binary exactly on chordal graphs, one can read the theorem as a polyhedral certificate of chordality: linear programming over these simple systems detects whether a graph is chordal, independent of graph-theoretic recognition algorithms."],"forward_implications":["For every chordal graph, the induced tree polytope is the intersection of C_T(G) with x(V)-y(E)=1; since C_T(G) has O(|V||K|) inequalities, the maximum-weight induced tree problem is solvable in polynomial time.","For every chordal graph, the induced path polytope is the intersection of C_P(G) with the same hyperplane; despite the exponential naive system, the non-dominated inequalities number O(|V|^2), so a compact extended formulation exists and the maximum-weight induced path problem is polynomial-time solvable.","Both polytopes have the integer decomposition property in chordal graphs, meaning every integer point of k times the polytope is a sum of k incidence vectors of induced trees or induced paths.","An inequality (5) is facet-defining exactly when no connected component of G[C(K∪{w})] is bipartite, which tells which of the exponentially many path inequalities are actually essential.","The characterization is sharp: if G is not chordal, T(G) and P(G) are not binary, so the simple hyperplane description itself detects chordality."],"fun_headline_variants":["Hilbert basis makes induced tree/path optimization polynomial on chordal","Extended formulations for induced tree/path polytopes on chordal","One hyperplane and Hilbert basis: tree/path polytopes on chordal","Hilbert basis yields polynomial-time optimization for chordal induced tree/path","Chordal graphs: compact and exponential formulations for tree/path polytopes"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that two induced paths in a chordal graph that share an endpoint can always be recombined cleanly: either their second vertices are adjacent, or the union of the two paths is again an induced path; the whole path Hilbert-basis argument rests on this recombination fact and on the edge-contraction argument that proves it.","fun_headline_variants_meta":{"raw":{"variants":["Hilbert basis makes induced tree/path optimization polynomial on chordal","Extended formulations for induced tree/path polytopes on chordal","One hyperplane and Hilbert basis: tree/path polytopes on chordal","Hilbert basis yields polynomial-time optimization for chordal induced tree/path","Chordal graphs: compact and exponential formulations for tree/path polytopes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001188,"raw_usage":{"total_tokens":4720,"prompt_tokens":700,"completion_tokens":4020,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":444,"completion_tokens_details":{"reasoning_tokens":3921}},"tokens_in":444,"tokens_out":4020,"duration_ms":27341,"temperature":1.0,"reasoning_tokens":3921,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T17:39:36.853201+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The theorems predict that for any chordal graph the polytope T(G) or P(G) has only binary extreme points and that every integer point of the cone is an integer conic combination of incidence vectors. A single counterexample to either statement — found by brute-force enumeration on small chordal graphs, or a non-chordal graph for which T(G) or P(G) is nonetheless binary — would refute the characterization. A more surgical check: search for two induced paths in a chordal graph sharing an endpoint whose second vertices are nonadjacent and whose union is not an induced path; such a pair would viol","supporting_citations":[],"review_version":1}