REVIEW 3 major objections 3 minor 9 references
A Constraint Model for the Tree Decomposition of a Graph
T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [5, Proposition] 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.
- [5, search procedure] 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.
- [3.2, constraint (16)] 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.
minor comments (3)
- [Throughout] 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'.
- [3.1] 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.
- [2 and 5] 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.
Circularity Check
No circularity: the constraint model directly encodes the definition of tree decomposition, and the search procedure makes no fitted or self-cited predictions.
full rationale
The derivation chain is self-contained. Constraints (6)-(16) in Section 3 are direct encodings of the defining properties of a tree decomposition: width bound (|N_i| <= w), vertex coverage (union of N_i = V), edge coverage (each edge appears in some node), and running intersection (intersection_{i,k} subset N_parent_k for the deeper node), together with parent/depth invariants for a rooted tree. The paper's central claim is that a sequence of decision problems over (m,w) finds treewidth and returns a witness; this is a search over existence problems, not a prediction inferred from fitted constants. No parameter is fitted to data, no empirical quantity is renamed as a prediction, and no uniqueness theorem is imported. The only self-citation, [8] (Prosser & Unsworth), is explicitly not used: 'This is one of the reasons why we did not use the tree constraint (such as [8]).' Hence it is not load-bearing. The Section 5 completeness proof has a correctness gap (the stated bound m <= n - w + 1 is asserted with a proof sketch that does not establish existence at exactly the m tried, and the w=2 stopping rule can misreport edgeless graphs), but an incomplete proof is a correctness issue, not circularity: the constraints do not presuppose the answer they seek. No circular step can be exhibited, so the score is 0.
Assumptions & free parameters
assumptions (3)
- standard math The definition of a tree decomposition and treewidth used in Section 2 (properties 1 to 4).
- domain assumption Constraint 16 enforces the running intersection property for all triples of nodes.
- domain assumption For completeness of the search process, any width-w tree decomposition can be padded with empty or duplicate nodes to reach exactly m = n−w+1 nodes.
Cite this review
Pith. "Pith review of A Constraint Model for the Tree Decomposition of a Graph." pith.science (2026). https://pith.science/paper/QUAIHEIC
@misc{pith2026190802530,
author = {Pith},
title = {Pith review of: A Constraint Model for the Tree Decomposition of a Graph},
year = {2026},
howpublished = {\url{https://pith.science/paper/QUAIHEIC}},
note = {Machine review of arXiv:1908.02530}
}
read the original abstract
We present a constraint model for the problem of producing a tree decomposition of a graph. The inputs to the model are a simple graph G, the number of nodes in the desired tree decomposition and the maximum cardinality of each node in that decomposition. Via a sequence of decision problems, the model allows us to find the tree width of a graph whilst delivering a tree decomposition of that width, i.e. a witness.
Figures
Reference graph
Works this paper leans on
-
[1]
M. Abseher, N. Musliu, and S. Woltran. htd - A free, open-source framework for (customized) tree decompositions and beyond. In Integration of AI and OR Tech- niques in Constraint Programming - 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings , pages 376–386, 2017
work page 2017
-
[2]
H. L. Bodlaender. A tourist guide through treewidth. Acta Cybern., 11(1-2):1–21, 1993
work page 1993
-
[3]
H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. , 25(6):1305–1317, 1996
work page 1996
-
[4]
H. L. Bodlaender, F. V. Fomin, A. M. C. A. Koster, D. Kratsch, and D. M. Thilikos. On exact algorithms for treewidth. ACM Trans. Algorithms, 9(1):12:1–12:23, 2012
work page 2012
-
[5]
R. Dechter. Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition. Artif. Intell., 41(3):273–312, 1990
work page 1990
-
[6]
R. Dechter and J. Pearl. Tree clustering for constraint networks. Artif. Intell. , 38(3):353–366, 1989
work page 1989
-
[7]
V. Gogate and R. Dechter. A complete anytime algorithm for treewidth. In UAI ’04, Proceedings of the 20th Conference in Uncertainty in Artificial Intelligence, Banff, Canada, July 7-11, 2004 , pages 201–208, 2004
work page 2004
-
[8]
P. Prosser and C. Unsworth. Rooted tree and spanning tree constraints. In 17th ECAI Workshop on Modelling and Solving Problems with Constraints , 2006
work page 2006
Show all 9 references
-
[9]
Prud’homme, J.-G
C. Prud’homme, J.-G. Fages, and X. Lorca. Choco documentation, 2017
2017
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.