{"id":"180c760d-3e3d-4858-980d-a647bfc7300c","arxiv_id":"1908.02530","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A constraint model with set and integer variables encodes tree decompositions, and a sequence of decision problems over node count and width finds the treewidth while producing a witness.","lead":"The paper presents a constraint programming model that encodes the definitions of a tree decomposition directly into set and integer variables, allowing a solver to find a tree decomposition of a given width or report that none exists. It is offered as a pedagogical and extensible tool rather than a competitive solver, useful for exploring treewidth and adding side constraints.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stated completeness is false as written: the §5 bound m ≤ n−w+1 has a counterexample, and the w=2 stopping rule misreports edgeless graphs as treewidth 1.","rationale":"Reading in good faith, the constraint model itself is a reasonable direct encoding of the definition, and constraints 6-15 plus 16 appear to make the decision problem sound (modulo the typo in constraint 16). The load-bearing weakness is the completeness of the search procedure in Section 5. The published proof is not merely incomplete; its central proposition is false, with an explicit small counterexample. The edgeless-graph failure shows the described algorithm outputs the wrong treewidth for a class of instances. However, both defects appear repairable: continue the sequence to w=1 or special-case edgeless graphs, and replace the proof by the standard maximal-clique-count argument for a chordal completion. The reader's CONDITIONAL verdict is therefore the right level: acceptance should be contingent on fixing the stopping rule and proving the exact bag-count lemma. My concern does not move the verdict, so I mark UNCHANGED.","tokens_in":4149,"tokens_out":37810,"duration_ms":369048,"concrete_test":"Enumerate all simple graphs on up to 7 vertices, run the described decision sequence (m=n+1−w, w from n down to 2), and compare the reported optimum w−1 with true treewidth computed by exhaustive search. The 4-vertex edgeless graph is the minimal expected failure: the sequence will find the valid width-2 decomposition {1,2}, {2,3}, {3,4} and stop at w=2, returning 1 instead of 0. If this is the only mismatch, the fix is to test w=1 and supply the missing exact-bag-count proof; any additional mismatch would falsify the central claim more broadly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5's completeness argument rests on a proposition that is false. The path P5 admits the duplicate-free width-2 decomposition whose bags are {1,2}, {2,3}, {3,4}, {4,5}, {5} arranged as a path; this has m=5 while n−w+1=4, refuting the stated upper bound. The intended saving claim, that a width-w decomposition can always be padded or merged to exactly m=n+1−w bags, is not proved, and empty-bag padding is not mentioned in the proof. Separately, the stopping rule 'repeat until w=2' is wrong for edgeless graphs: for n≥2 isolated vertices there is a valid width-2 decomposition with m=n−1 (bags {i,i+1} in a path), so the sequence stops and reports treewidth 1 although the true treewidth is 0. A correct completeness proof would need, for every w above the optimum, a width-w decomposition with at most n+1−w bags, e.g., from a chordal completion whose maximal cliques number at most n−w+1; no such argument appears.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a constraint programming model that encodes the definition of a tree decomposition directly: set variables for bags, parent/depth variables for the tree structure, location variables for edge coverage, and intersection variables for the running intersection property. The authors propose a sequence of decision problems with m nodes and width w, increasing m while decreasing w, and claim the process is sound and complete, with a proof sketch based on a bound m ≤ n−w+1 for duplicate-free decompositions. They report timings for one small example and explicitly position the model as pedagogical rather than competitive.","tokens_in":4355,"tokens_out":12721,"duration_ms":133383,"significance":"If the correctness claim were established, the paper would provide a clean, easily modifiable CP encoding of tree decomposition, useful for teaching and for adding side constraints such as pathwidth. The authors are honest about the model's poor performance. However, the central search procedure is currently not correct: the supporting proposition is false and the stopping rule misclassifies edgeless graphs. These are load-bearing issues for the paper's main claim of finding treewidth and a witness.","major_comments":[{"comment":"The proposition 'If T is a tree decomposition of m nodes and width w of graph G, with no duplicate nodes, then m ≤ n−w+1' is false. For the path P5, the bags {1,2}, {2,3}, {3,4}, {4,5}, {5} form a duplicate-free tree decomposition of width 2 with m=5, while n−w+1=4. The proof's claim that every node must contain an 'unseen' vertex is invalid (the last bag contains no such vertex). Consequently, the completeness argument for the search process does not go through: the procedure only tests pairs with m=n+1−w, and the paper never proves that whenever a width-w decomposition exists, one exists with exactly (or at most) n+1−w bags.","section":"5, Proposition"},{"comment":"The stopping rule 'repeat until w = 2 (in which case G is a tree)' is incorrect. For an edgeless graph on n≥2 vertices, a width-2 decomposition with m=n−1 bags exists, e.g., a path whose bags are pairs of vertices; hence the procedure stops at w=2 and reports treewidth 1 even though the true treewidth is 0. The condition w=2 is therefore not equivalent to G being a tree. The procedure needs to continue to w=1 (or handle the edgeless case explicitly) to return the correct minimum width.","section":"5, search procedure"},{"comment":"Constraint (16) is written as '∀i,k∈[0..m−1], i≠j depth_i ≤ depth_k ⇒ intersection_i,k ⊆ N_parent_k', but j is not a bound variable. This appears to be a typo for i≠k. As printed, the constraint is ill-formed and cannot be encoded. Because this is the constraint that enforces the running intersection property, the typo must be corrected for the model to be sound and verifiable.","section":"3.2, constraint (16)"}],"minor_comments":[{"comment":"There are several typos: 'refered' should be 'referred', 'decompostion' should be 'decomposition', 'resticts' should be 'restricts', 'pratical' should be 'practical', and the Section 3 heading 'V ariables' should be 'Variables'.","section":"Throughout"},{"comment":"The text refers to the intersection variables as '(4) above', but the correct equation number for the intersection variables is (5); this cross-reference should be fixed.","section":"3.1"},{"comment":"The distinction between model width w (maximum bag size) and conventional treewidth (w−1) should be stated explicitly in the stopping-rule discussion, since the current wording contributes to the incorrect edgeless-graph classification.","section":"2 and 5"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a short, workshop-style paper. The CP encoding itself is plausible, but the search procedure's correctness is not established, and the current stopping rule gives wrong answers for edgeless graphs. In my view these issues are fixable within the scope of the paper: the authors should correct the stopping rule, provide a valid proof of the existence of a decomposition with the exact number of bags used by the search (e.g., via empty-bag padding once a suitable upper bound is shown), and fix the constraint (16) quantifier typo. I do not think the paper should be accepted in its present form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is the first constraint programming model for tree decomposition, and that part is mostly solid. The encoding follows the definition directly: set variables for bags, parent and depth variables for the tree, bitset channeling, an element constraint over an array of sets for the running intersection property. Constraints 6–15 are standard. Constraint 16 looks like a workable way to enforce running intersection in a rooted tree, modulo the obvious typo (i≠j should be i≠k). The authors are also honest that the approach is orders of magnitude slower than dedicated solvers and position it as a teaching tool and an extensible template. That is a fair and useful framing.\n\nThe problem is Section 5. The search procedure tries only m = n – w + 1 bags for each width w, and the proof of completeness rests on the proposition that any duplicate-free width-w decomposition has at most n – w + 1 nodes. That proposition is false. A path on 5 vertices has a duplicate-free width-2 decomposition with 5 bags: {1,2}, {2,3}, {3,4}, {4,5}, {5}. This satisfies all four defining properties and has no duplicate bags. So the stated upper bound m ≤ n – w + 1 fails. Consequently, the search can miss valid decompositions that use more bags, and the claimed completeness is unsupported. The stress-test note is right about this.\n\nThe stopping rule at w = 2 has a separate bug: for an edgeless graph on n ≥ 2 vertices, there is a valid width-2 decomposition with n – 1 bags (e.g., {i, i+1} in a path), so the loop stops and reports treewidth 1, though the true treewidth is 0. That is a concrete misclassification. A correct procedure would need to try w = 1 as well, or otherwise handle graphs with no edges.\n\nEverything else is comparatively minor. There are no experimental comparisons, no code or data, but the authors openly say so and do not claim practical competitiveness. The citation pattern looks fine; the “first CP model” claim is plausible given their literature review.\n\nWho should read this: CP researchers curious about modeling treewidth, and anyone teaching tree decompositions. It is a short, readable sketch rather than a complete algorithmic treatment. The model itself could be fixed with a correct completeness argument (e.g., bounding the minimum number of bags and padding, or a different search order) and by handling w = 1. As it stands, the central correctness claim is broken, so it needs major revision before acceptance. It does deserve serious peer review, because the encoding is new and the flaws are fixable.\n\nRecommendation: send to a referee, but expect the authors to repair the completeness proof and the stopping rule.","headline":"A clean CP encoding of tree decomposition that is honest about being slow, but the claimed completeness of the search is false as written and the w=2 stopping rule misreports edgeless graphs.","tokens_in":4871,"tokens_out":5731,"would_cite":false,"duration_ms":64676,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68R10","68T20"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single constraint model, driven through a sequence of decision problems, finds a graph's treewidth and hands back a tree decomposition that certifies it.","keywords":["Tree Decomposition","Tree Width","Constraint Programming Model","Running Intersection Property","Decision Problems","Witness","Exact Computation","Graph Algorithms"],"falsifier":"Run the model on a single-edge graph with n=2, w=2, and m=3: a padded decomposition {u}, {u,v}, {v} is valid, yet m exceeds the paper's claimed bound n−w+1=1. If the model rejects this instance, it cannot pad, so the sequential search can falsely report failure at m=n−w+1 for graphs whose width-w decompositions have fewer nodes; if it accepts, the bound is false and the completeness proof must be revised. Either outcome pinpoints the gap in the paper's completeness argument.","tokens_in":3959,"feed_emoji":"🌲","tokens_out":14034,"duration_ms":141635,"temperature":0.7,"pith_summary":"The paper claims that treewidth—the minimum bag size of a tree decomposition of a graph—can be computed with a plain constraint model, and that the same model always delivers a witness: an explicit tree decomposition of that width. Each call to the model takes a graph, a target number m of tree nodes, and a width bound w, and decides whether a valid decomposition with those parameters exists. By walking through a short sequence of such decision problems, starting with m=1 and w=n and stepping toward smaller w, the model both identifies the treewidth and produces the decomposition proving it. The authors are careful to say the model is orders of magnitude slower than dedicated treewidth algorithms; their claim is that it is simple, portable, and easily adapted to side constraints, making it useful for exploring and explaining treewidth.","feed_headline":"A constraint model finds treewidth and returns the tree","feed_subtitle":"A short sequence of decision problems produces both the width and an explicit decomposition that proves it.","key_machinery":"The working heart of the paper is constraint 16, which encodes the running intersection property in a local way: whenever node i is no deeper than node k, the intersection of Ni and Nk must be a subset of the parent of Nk. Together with the width constraint |Ni| ≤ w, the edge-coverage constraints, and the parent/depth constraints that build a rooted tree, this turns tree-decomposition existence into a constraint satisfaction problem over set and integer variables. The sequential search's completeness is intended to follow from the bound m ≤ n−w+1 for duplicate-free decompositions, which says the number of tree nodes never needs to exceed n−w+1, so the particular m tried at each width covers all possible decompositions.","core_discovery":"The central claim is that for any simple graph G, the constraint model decides satisfiability of a tree decomposition with exactly m nodes, each node containing at most w vertices, subject to the four defining properties: every vertex of G appears in at least one node, every edge is contained in some node, and the running intersection property holds (for any three nodes i, j, k with j on the path from i to k, the intersection of nodes i and k is a subset of node j). The model encodes these properties using set variables for the nodes and their pairwise intersections, integer variables for parent and depth in a rooted tree, and Boolean variables for edge membership. The paper asserts the resulting sequence of decision problems is sound and complete, so the last satisfiable pair (m,w) gives the treewidth and a witness decomposition. The authors support completeness with a proof sketch based on a bound m ≤ n−w+1 on the number of nodes in any duplicate-free decomposition of width w.","pith_inferences":["The same decision-sequence template could be adapted to other width parameters—branchwidth, cutwidth, or pathwidth—by swapping the constraints that define the decomposition family, since the model's structure is parameter-agnostic.","If padding with empty bags is permitted, completeness would hold even without the tight bound m ≤ n−w+1; the paper's proof sketch is stronger than needed, and an explicit padding lemma would simplify the correctness argument.","A natural benchmark would pit this model against modern exact treewidth solvers on graphs of 10–20 vertices to quantify the reported slowdown and identify where the declarative approach becomes impractical.","One could augment the model to emit a certificate of optimality, such as an elimination ordering, by adding constraints that couple the decomposition to a vertex-ordering—an extension the paper does not pursue."],"forward_implications":["If the process is sound and complete, then exact treewidth computation and witness generation are achievable with generic constraint-programming primitives, without bespoke treewidth algorithms.","The sequential decision process terminates within at most n−1 steps, returning both a treewidth value and a concrete decomposition of that width.","The model is deliberately easy to alter: the paper notes that changing the parent constraint to parent_i = i−1 turns it into a pathwidth search.","Because the constraints are declarative, additional side constraints (e.g., forcing specified vertices into the same bag) can be added without restructuring the model.","The authors state the model runs orders of magnitude slower than state-of-the-art algorithms, so its intended use is exploratory and educational rather than competitive."],"supporting_citations":[{"why":"Standard survey defining tree decomposition and treewidth; establishes the problem the model solves.","marker":"[2]"},{"why":"Describes a linear-time algorithm for small treewidth; represents the algorithmic baseline this CP approach is contrasted with.","marker":"[3]"},{"why":"Surveys exact algorithms for treewidth; provides the exact-computation context for the sequential decision process.","marker":"[4]"},{"why":"Presents a complete anytime algorithm for treewidth; the completeness claim of the decision sequence is measured against this standard.","marker":"[7]"},{"why":"Documentation of the constraint programming toolkit used to implement and run the model; grounds the claim that the model uses only standard CP primitives.","marker":"[9]"}],"fun_headline_variants":["Constraint model computes treewidth and its witness","Treewidth via constraints: model returns explicit decomposition","New constraint approach gives treewidth and proof structure","Deciding treewidth with constraints: witness guaranteed","Constraint satisfaction finds treewidth and builds witness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sequential search is complete only if any tree decomposition can be padded—by adding extra, possibly empty or subset nodes—up to the exact number of nodes m tried at each step; the paper neither states nor proves that padding property, and its bound-based completeness argument does not apply to decompositions that contain redundant or subset bags.","fun_headline_variants_meta":{"raw":{"variants":["Constraint model computes treewidth and its witness","Treewidth via constraints: model returns explicit decomposition","New constraint approach gives treewidth and proof structure","Deciding treewidth with constraints: witness guaranteed","Constraint satisfaction finds treewidth and builds witness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000255,"raw_usage":{"total_tokens":1491,"prompt_tokens":787,"completion_tokens":704,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":403,"completion_tokens_details":{"reasoning_tokens":635}},"tokens_in":403,"tokens_out":704,"duration_ms":6976,"temperature":1.0,"reasoning_tokens":635,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:42:57.069412+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the model on a single-edge graph with n=2, w=2, and m=3: a padded decomposition {u}, {u,v}, {v} is valid, yet m exceeds the paper's claimed bound n−w+1=1. If the model rejects this instance, it cannot pad, so the sequential search can falsely report failure at m=n−w+1 for graphs whose width-w decompositions have fewer nodes; if it accepts, the bound is false and the completeness proof must be revised. Either outcome pinpoints the gap in the paper's completeness argument.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Standard survey defining tree decomposition and treewidth; establishes the problem the model solves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Describes a linear-time algorithm for small treewidth; represents the algorithmic baseline this CP approach is contrasted with."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Surveys exact algorithms for treewidth; provides the exact-computation context for the sequential decision process."},{"cited_title":"Gogate and R","cited_arxiv_id":null,"evidence_quote":"Presents a complete anytime algorithm for treewidth; the completeness claim of the decision sequence is measured against this standard."},{"cited_title":"Prud’homme, J.-G","cited_arxiv_id":null,"evidence_quote":"Documentation of the constraint programming toolkit used to implement and run the model; grounds the claim that the model uses only standard CP primitives."}],"review_version":1}