Partial k-tree¶

A graph that embeds as a subgraph of a k-tree, equivalently one whose treewidth is at most k.

Version: v2 · 2026-09-07 · History
Domain-specific #: 2454
Origin domain: graph theory
Subdomain: structural graph theory
Aliases: Graph of treewidth at most k, Bounded-treewidth graph at bound k

Core Idea¶

A partial k-tree is an undirected graph that is a subgraph of a k-tree. Equivalently, it is a graph whose treewidth is at most the fixed nonnegative integer k. The two descriptions expose complementary aspects of the same object. The completion description says that missing edges may be added until the graph has the maximally tree-like recursive form of a k-tree. The decomposition description says that the graph can be covered by small, locally coordinated vertex sets—bags of size at most k + 1—arranged along a tree.

The word partial refers to the subgraph relation, not to an unfinished tree and not to an incompletely specified graph. A partial k-tree may contain cycles, cliques, disconnected components, and graph-theoretic structures that look little like ordinary trees. What remains tree-like is its global pattern of interaction: every edge is witnessed inside a small bag, and the bags containing any one vertex form a connected subtree.

The parameter is an upper bound. A graph of treewidth j less than k is still a partial k-tree. Authors who use “partial k-tree” to mean minimal k should state that additional convention; the standard at-most-k reading is the safer catalog identity.

Structural Signature¶

Let G = (V, E) be a finite undirected graph and let k be fixed. A tree decomposition of G consists of a tree T and a bag B_t contained in V for each node t of T. It must satisfy three conditions:

every vertex of G occurs in at least one bag;
the endpoints of every edge of G occur together in some bag; and
for each vertex v, the nodes t whose bags contain v induce a connected subtree of T.

The width of the decomposition is the size of its largest bag minus one. The treewidth of G is the minimum width over all its tree decompositions. G is a partial k-tree exactly when it has some decomposition of width at most k.

The equivalent completion signature begins with a k-tree: under a common convention, start from a clique of size k + 1 and repeatedly add a vertex adjacent to all vertices of an existing k-clique^[1]. A graph is a partial k-tree when it can be obtained as a subgraph of such a graph. Starting-clique conventions differ for very small graphs, but they do not disturb the treewidth-at-most-k characterization.

The mandatory roles are therefore: a graph under classification; a fixed bound k; and either a containing k-tree or a width-at-most-k decomposition that certifies membership. The invariant is not any particular drawing or decomposition. It is the existence of at least one valid certificate meeting the bound.

What It Is Not¶

A partial k-tree is not necessarily a k-tree. A k-tree is edge-maximal at its treewidth under the recursive construction; a partial k-tree can have edges removed and need not be chordal or maximal. Conversely, every k-tree is a partial k-tree.

It is not a tree except in a low-bound special case. Partial 1-trees are forests, whereas partial 2-trees can already contain cycles and triangles. It is not defined by planarity: many familiar bounded-treewidth families are planar, but bounded treewidth neither entails planarity in general nor follows from planarity. Large planar grids have unbounded treewidth, and bounded-treewidth classes at suitable k include nonplanar graphs^[2].

It is not pathwidth. A path decomposition requires the decomposition tree to be a path and is therefore more restrictive. Nor is it clique-width, branchwidth, bandwidth, degeneracy, or any other graph-width parameter, even when inequalities connect those measures.

Finally, “treewidth at most k” must not be silently changed to “treewidth exactly k.” The first describes a nested class; the second describes one layer of that nesting.

Scope of Application¶

Partial k-trees belong to structural graph theory, graph-minor theory, parameterized complexity, and algorithm design. They provide a common language for graph families that may look different locally but all admit bounded-width decompositions. Forests, cactus graphs, pseudoforests, series-parallel graphs, outerplanar graphs, and several recursively constructed network families occur within bounded partial-k-tree classes, although the smallest suitable k differs.

The abstraction is especially useful when k is fixed or small relative to graph size. Algorithms can organize computation around the decomposition tree, retaining only the information that crosses each bag. This is a recurring technique for otherwise difficult optimization, counting, and decision problems. The resulting dependence on the number of vertices may be polynomial or linear for fixed k, while the hidden dependence on k and on the problem can be exponential.

The class also appears when a domain-specific graph construction guarantees bounded treewidth. Thorup showed that control-flow graphs of structured programs have small treewidth and used the property in register-allocation analysis^[3]. The abstraction thereby connects a syntactic restriction on programs to a structural certificate and then to an algorithmic strategy.

Clarity¶

The fastest recognition question is: “Can this graph be certified by bags of size no more than k + 1 satisfying coverage, edge containment, and running intersection?” If yes, it is a partial k-tree. A proposed decomposition with one bag of size k + 2 does not prove failure, because a different, narrower decomposition might exist. Treewidth is a minimum over all valid decompositions.

A second diagnostic asks whether edges can be added to place the graph inside a k-tree. This is completion, not arbitrary resemblance. Removing edges from a k-tree preserves partial-k-tree membership because it preserves the subgraph witness, even though the result may lose chordality.

Three quick boundary tests help. A forest is a partial 1-tree. A graph containing K4 as a minor is not a partial 2-tree. A graph with a displayed width-k decomposition is a partial k-tree even if it has lower treewidth; the display certifies only an upper bound.

Manages Complexity¶

An arbitrary graph can connect distant regions in ways that force a global algorithm to remember a large interface. A width-k decomposition bounds each interface by at most k + 1 vertices. Dynamic programming can summarize each processed subtree by a table indexed by states on its current bag, combine compatible child summaries, and eventually recover a whole-graph answer at the root.

This compression explains both the power and the price of the abstraction. For fixed k, a state space exponential in k is constant with respect to graph size, making many computations tractable. When k grows, the same tables can become prohibitive. Bounded treewidth is therefore not a universal promise that every problem becomes easy, and it does not include the cost of finding or validating a suitable decomposition unless that step is supplied by the algorithmic setting.

The completion view manages classificatory complexity as well. Many apparently distinct graph families can be placed under a common bounded-treewidth ceiling, allowing theorems and algorithms to be stated once for partial k-trees instead of separately for every family.

Abstract Reasoning¶

The abstraction licenses several reliable inferences. A width-at-most-k decomposition proves partial-k-tree membership. A graph minor of a partial k-tree remains a partial k-tree because deleting or contracting edges cannot increase treewidth. Consequently, for each fixed k, the class is minor-closed and has a finite forbidden-minor characterization, although the obstruction set becomes complicated as k increases^[4].

Membership also bounds local density. A partial k-tree is a subgraph of a k-tree, so it is k-degenerate and can be colored with at most k + 1 colors. Its clique number is at most k + 1. These are consequences, not definitions: many sparse or easily colorable graphs still have treewidth exceeding k.

For algorithm design, the key inference is conditional: if the desired partial solution can be summarized entirely by its interaction with the current bag, then the tree decomposition supports bottom-up dynamic programming. One must still define sufficient states, transition rules, and reconstruction information. “Bounded treewidth” does not replace that problem-specific proof.

Knowledge Transfer¶

The transferable pattern is small separators arranged in a tree. In graph algorithms, a bag is a bounded interface between an already processed region and the rest of the graph. Similar interface-based reasoning appears in constraint satisfaction, probabilistic graphical models, database joins, circuit reasoning, and program analysis when their interaction structures have bounded treewidth.

The transfer is exact only when the receiving object is represented by an appropriate graph and the algorithm’s dependencies respect the decomposition. Calling a hierarchy, organization, or narrative “tree-like” does not make it a partial k-tree. The mathematical commitments—vertices, edges, a fixed bound, valid bags, and running intersection—must be present.

Partial-k-tree reasoning can also move between structural and operational views. A family-specific theorem may establish bounded treewidth; a decomposition algorithm then produces a certificate; and a dynamic program exploits that certificate. Keeping these steps distinct prevents a common error in which family membership, decomposition availability, and problem tractability are treated as the same claim.

Examples¶

Forests. Every forest has treewidth at most one, so it is a partial 1-tree. A tree decomposition can use one two-vertex bag for each edge, arranged compatibly with the forest. A triangle is the single forbidden minor for this class^[2].

Partial 2-trees. Graphs of treewidth at most two are exactly the partial 2-trees and are characterized by exclusion of K4 as a minor^[2]. Series-parallel graphs lie in this class; under the standard componentwise formulation, a graph is a partial 2-tree exactly when each biconnected component is series-parallel.

Outerplanar graphs. Outerplanar graphs have treewidth at most two and are therefore partial 2-trees. The converse fails: being a partial 2-tree does not by itself impose an outerplanar embedding.

A structured program. Construct the program’s control-flow graph. A bounded-width decomposition creates small interfaces between regions. Register-allocation or other dataflow-related computations can propagate summaries across those interfaces. The program is not called a partial k-tree; its control-flow graph is.

A nonexample. The n-by-n grid has treewidth n up to the usual indexing convention^[2]. No fixed k contains all grids as partial k-trees, despite every grid being planar and sparse. This cleanly separates planarity and bounded treewidth.

Structural Tensions¶

Generality versus algorithmic leverage. Increasing k admits more graphs but expands the interfaces and state spaces that algorithms must handle. A loose bound may certify membership while yielding little practical speed.

Existence versus construction. The class identity needs only the existence of a suitable decomposition or completion. An implementation needs an explicit certificate. A theorem that the graph family has bounded treewidth and an algorithm that finds useful bags are separate assets.

Maximal completion versus original structure. Completing a graph to a k-tree exposes a clean recursive scaffold, but added edges are analytical devices and may not exist in the modeled system. Reasoning must not treat fill edges as original relationships.

Uniform class versus exact parameter. The label partial k-tree expresses an upper bound. Optimization and comparison may require the smallest such k, namely the graph’s treewidth. Confusing a certificate’s width with optimal treewidth can overstate structural complexity.

Structural–Framed Character¶

The abstraction is strongly structural within a graph-theoretic frame. Its roles—elements, pairwise relations, bounded interfaces, a tree of interfaces, and consistency of element occurrence—form a reusable skeleton. Yet literal identity depends on graph, subgraph, clique, decomposition, and treewidth definitions. It is therefore domain-specific rather than prime-level.

Its structural content is high because isomorphic graphs have the same status, and the characterization ignores semantic labels on vertices and edges. Its framed content remains decisive because transferring the phrase outside graph models without an explicit interaction graph destroys the membership test.

Structural Core vs. Domain Accent¶

The structural core is that a complex network can be assembled or analyzed through bounded overlaps arranged acyclically. Local regions communicate through small interfaces, and consistency is maintained along the unique paths of the interface tree. This core supports decomposition, locality, modular summaries, and controlled recombination.

The domain accent supplies exact graph-theoretic machinery: simple undirected graphs, k-trees, subgraphs, bags, edge coverage, running intersection, width, minors, and forbidden obstructions. These are not decorative terms. They determine whether a candidate belongs to the class and what conclusions follow.

The residue already maps to broad encyclopedia ideas such as Network, Decomposition, Constraint, Locality, and Hierarchy. None of those primes, alone or in combination, preserves the exact equality between subgraphs of k-trees and graphs of treewidth at most k, the small-k obstruction results, or the fixed-parameter algorithmic practice. That stable residue justifies a domain-specific node.

Partial k-tree strictly specializes Network: every instance is a graph-structured network, while most networks do not admit the specified bound. Decomposition is realized by the tree decomposition certificate. Constraint appears in the three decomposition axioms and the bag-size limit. Locality is operationalized through bag-bounded interfaces, and Hierarchy appears in the tree arrangement of those bags.

Only Network is proposed as the minimal DAG parent. The other primes explain mechanisms or perspectives rather than serving as necessary taxonomic parents. Keeping them as prose relations avoids multiplying edges that add interpretation but not classification.

Relationships to Other Abstractions¶

Current abstraction Partial k-tree Domain-specific

Parents (1) — more general patterns this builds on

Partial k-tree is a kind of Network Prime

Partial k-tree strictly specializes Network: every instance is a graph-structured network, while most networks do not admit the specified bound.

Hierarchy path (1) — routes to 1 parentless root

Partial k-tree → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space¶

Partial k-tree sits in a sparse region of the domain-specific corpus (86^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Pathwidth — 0.84
Treewidth — 0.81
SPQR Tree — 0.80
Cage (Graph Theory) — 0.79
Rank-width — 0.79

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

k-tree: the maximal recursive supergraph, not the full subgraph class.
Tree (Graph Theory): the k = 1 connected special case, not the general definition.
Tree decomposition: a certificate carried by a graph, not the graph itself.
Treewidth: the numerical minimum width, not the class of graphs below a selected bound.
Pathwidth: the more restrictive width obtained when the decomposition tree must be a path.
Planarity: an embedding property independent of any fixed treewidth bound.
Series-parallel graph: a prominent subfamily or componentwise characterization at k = 2, not the all-k concept.
Incomplete tree: an ordinary-language reading with no bearing on the graph-theoretic term.

References¶

[1] Rose, D. J. “On simple characterizations of -trees”. Discrete Mathematics, 1974. Rose's paper is the definitional origin of k-trees; its text was not reachable for this check, so the starting-clique convention attributed here rests on the sentence's own hedge rather than on verified wording. registry ↩

[2] Bodlaender, Hans L. “'A Partial k-Arboretum of Graphs with Bounded Treewidth.'”. Theoretical Computer Science, 1998. Bodlaender's survey supplies the first half: planar graphs, and n x n grids in particular, have arbitrarily large treewidth. The converse observation, that bounded-treewidth classes contain nonplanar graphs, is not drawn there. Bodlaender's survey states the characterization directly: a graph has treewidth at most 1 exactly when it has no K3 minor - one obstruction, against four already at k = 3. Bodlaender's survey carries both halves - treewidth at most 2 is exactly the partial 2-trees, and the class is precisely the K4-minor-free graphs - and, in the same theorem set, the componentwise series-parallel formulation. Bodlaender's survey gives the value under the same n-by-n indexing the sentence uses, proving the lower bound as Lemma 88; the hedge is about competing grid conventions elsewhere, not a disagreement with this source. registry ↩a ↩b ↩c ↩d

[3] Thorup. “All Structured Programs Have Small Tree Width and Good Register Allocation”. Information and Computation, 1998. Thorup's paper is the named source for both halves, and 'small' is its own word; the underlying result is a fixed constant bound (the follow-up literature reports treewidth at most 6 for goto-free structured programs), not merely an asymptotic smallness. registry ↩

[4] Robertson, Neil and Seymour, Paul D. “Graph Minors. XX. Wagner's Conjecture”. Journal of Combinatorial Theory, Series B, 2004. Robertson and Seymour's proof of Wagner's conjecture is what makes the forbidden-minor set finite; the minor-closure of the class and the growth in complexity of the obstruction sets are separate points not established here. registry ↩