Overview

Comparing parameterizations
Dynamical programming on trees (example: WEIGHTED INDEPENDENT SET / VERTEX COVER)
Path-width with FPT algorithm
Tree-width with FPT algorithm
FPT results for other problems using tree-width dynamic programming
Other width notions: clique-width, branch-width, rank-width, carving-width, cut-width, etc.
Relationships between width parameters

Foundations of Parameterized Complexity

First, recall: Parameterized Problems and Fixed-Parameter Tractability (FPT)

Comparing Parameterizations

For $\kappa_1, \kappa_2 : \Sigma^* \to \mathbb{N}$: - $\kappa_1 \succeq \kappa_2$ (computably bounded above) iff $\exists$ computable $g: \mathbb{N} \to \mathbb{N}$ s.t. $\forall x \in \Sigma^*, g(\kappa_1(x)) \ge \kappa_2(x)$. - $\kappa_1 \approx \kappa_2$ iff $\kappa_1 \succeq \kappa_2$ and $\kappa_2 \succeq \kappa_1$. - $\kappa_1 \succ \kappa_2$ iff $\kappa_1 \succeq \kappa_2$ and not $\kappa_2 \succeq \kappa_1$.

Proposition: If $\kappa_1 \succeq \kappa_2$, then:

$\langle Q, \kappa_2 \rangle \in \mathsf{FPT} \;\Rightarrow\; \langle Q, \kappa_1 \rangle \in \mathsf{FPT}$
$\langle Q, \kappa_1 \rangle \notin \mathsf{FPT} \;\Rightarrow\; \langle Q, \kappa_2 \rangle \notin \mathsf{FPT}$

This allows transferring algorithmic (or hardness) results between different graph width parameters.

Notions of Graph Width

Path-width

Definition (Robertson and Seymour 1983)
A path decomposition of $G = \langle V, E \rangle$ is a sequence of bags $\langle B_1, B_2, \dots, B_r \rangle$, $B_i \subseteq V$, satisfying:

(P1) Vertex coverage: $\bigcup_{i=1}^r B_i = V$.
(P2) Edge coverage: $\forall \{u,v\} \in E, \exists i: \{u,v\} \subseteq B_i$.
(P3) Interval property: for every $v \in V$, the set of indices $i$ with $v \in B_i$ forms a contiguous interval $[i_{\min}, i_{\max}]$.

The width of the decomposition is $\max_{1 \le t \le r} |B_t| - 1$. The path-width of $G$, denoted $pw(G)$, is the minimum width over all path decompositions of $G$.

Nice path decomposition: A path decomposition is nice if:

$B_1 = B_r = \emptyset$;
For every $i > 1$, either
introduce step: $B_i = B_{i-1} \cup \{v\}$ with $v \notin B_{i-1}$, or
forget step: $B_i = B_{i-1} \setminus \{v\}$ with $v \in B_{i-1}$.

Lemma: From any path decomposition of width $k$ one can construct a nice path decomposition of the same width in time $O(k^2 \cdot \max\{r, n\})$.

Separation property: For $i \in [1, r-1]$, let $A = \bigcup_{j=1}^i B_j$, $B = \bigcup_{j=i+1}^r B_j$. Then $\langle A, B \rangle$ is a separation of $G$ with separator $B_i \cap B_{i+1}$; i.e., $V = A \cup B$ and there are no edges between $A \setminus B$ and $B \setminus A$. The border $\partial(A)$ of $A$ is the set of vertices in $A$ that have a neighbor in $V \setminus A$.

Tree-width

Definition (Bertelé and Brioschi 1972; Halin 1976; Robertson and Seymour 1984)
A tree decomposition of $G = \langle V, E \rangle$ is a pair $\langle T, \{B_t\}_{t \in T} \rangle$ where $T = \langle T, F \rangle$ is a tree and each node $t$ holds a bag $B_t \subseteq V$, satisfying:

(T1) $\bigcup_{t \in T} B_t = V$.
(T2) For every edge $\{u,v\} \in E$, there exists $t \in T$ with $\{u,v\} \subseteq B_t$.
(T3) For every $v \in V$, the nodes $\{t \in T \mid v \in B_t\}$ induce a connected subtree of $T$.

Width: $\max_{t \in T} |B_t| - 1$. The tree-width $tw(G)$ is the minimum width over all tree decompositions.

Nice tree decomposition: Choose a leaf as root $r$ and orient away from $r$. The decomposition is nice if:

$B_r = \emptyset$, and $B_{\ell} = \emptyset$ for every leaf $\ell$.
Every non-leaf node $t$ is of one of three types:
Introduce node: one child $t'$, $B_t = B_{t'} \cup \{v\}$ (vertex $v$ introduced).
Forget node: one child $t'$, $B_t = B_{t'} \setminus \{w\}$ (vertex $w$ forgotten).
Join node: two children $t_1, t_2$, with $B_t = B_{t_1} = B_{t_2}$.

Lemma: From any tree decomposition of width $k$ one can construct a nice tree decomposition of the same width with $O(k n)$ nodes in time $O(k^2 \cdot \max\{r,n\})$.

Separation property: Removing an edge $e = (a,b)$ from $T$ splits it into subtrees $T_a$ and $T_b$. Setting $A = \bigcup_{t \in V(T_a)} B_t$, $B = \bigcup_{t \in V(T_b)} B_t$ yields a separation $\langle A, B \rangle$ with separator $B_a \cap B_b$.

Complexity: Deciding $tw(G) \le k$ is NP-complete. However, the parameterized problem (p-TREE-WIDTH) is FPT; there exist algorithms running in time $2^{p(k)} \cdot n$ (e.g., Bodlaender’s linear-time algorithm for fixed $k$).

Clique-width

Definition (Courcelle, Engelfriet, Rozenberg 1993)
For $k \in \mathbb{N}$, a $k$-expression is built from:

\[ \varphi, \varphi_1, \varphi_2 ::= i \mid \text{edge}_{i \to j}(\varphi) \mid \text{recolor}_{i \to j}(\varphi) \mid (\varphi_1 \oplus \varphi_2) \]

with $i,j \in [k]$, $i \neq j$. Every $k$-expression $\varphi$ generates a labeled graph $G(\varphi)$:

$G(i)$: graph with a single vertex colored $i$.
$G(\text{edge}_{i \to j}(\varphi))$: add edges between all vertices of color $i$ and all vertices of color $j$ in $G(\varphi)$.
$G(\text{recolor}_{i \to j}(\varphi))$: change every vertex of color $i$ to color $j$ in $G(\varphi)$.
$G(\varphi_1 \oplus \varphi_2)$: disjoint union of $G(\varphi_1)$ and $G(\varphi_2)$.

The clique-width $clw(G)$ is the smallest $k$ such that $G$ can be defined (up to isomorphism) by a $k$-expression when ignoring the final colors.

Properties:

Cliques and stars have clique-width 2; trees have clique-width $\le 3$; $n \times n$ grids have clique-width $\Theta(n)$.
Clique-width is preserved under taking induced subgraphs, but not under taking general subgraphs (e.g., minors).
$clw(G) \le 3 \cdot 2^{tw(G)-1}$, but the converse fails: $clw(K_n)=2$ while $tw(K_n)=n-1$.
Deciding $clw(G) \le k$ is NP-hard; the parameterized problem is in XP, but unknown whether in FPT.
Every graph property expressible in MSO (monadic second-order logic) can be decided in linear time with respect to clique-width.

Other Width Notions via $f$-Width

A cut function or connectivity function $f: 2^U \to \mathbb{R}_0^+$ is symmetric ($f(X) = f(U \setminus X)$) and fair ($f(\emptyset)=f(U)=0$). Several width parameters are instances of branch-width for suitable connectivity functions.

Branch-width

For $G = \langle V, E \rangle$, define $f_{bw}: 2^E \to \mathbb{N}$ by $f_{bw}(X) = |\partial(X)|$, where $\partial(X)$ is the set of vertices incident to both an edge in $X$ and an edge in $E \setminus X$. The branch-width $bw(G)$ equals the branch-width of $(E, f_{bw})$.

Rank-width

For $G = \langle V, E \rangle$ and $X \subseteq V$, let $B_G(X)$ be the $X \times (V \setminus X)$ adjacency matrix over $\text{GF}(2)$; i.e., the bipartite adjacency matrix of the cut $X / V \setminus X$. Define $\rho_G(X) = \text{rank}_{\text{GF}(2)}(B_G(X))$. The rank-width $rw(G)$ is the branch-width of $(V, \rho_G)$.

Properties: $rw(G) \le tw(G)$; tree-width cannot be bounded by any function of rank-width (e.g., $rw(K_n)=1$, $tw(K_n)=n-1$).

Carving-width and Cut-width

For $X \subseteq V$, let $\text{cut}_G(X) = |\{ \{u,v\} \in E \mid u \in X, v \in V \setminus X \}|$.

Carving-width $carw(G)$: branch-width of $(V, X \mapsto |\text{cut}_G(X)|)$.
Cut-width $cutw(G)$: for an ordering $\pi$ of $V$, $\text{width}(\pi) = \max_{1 \le i \le n} |\text{cut}_G(\{\pi(1),\dots,\pi(i)\})|$; then $cutw(G) = \min_{\pi} \text{width}(\pi)$.

Dynamic Programming Algorithms

Weighted Independent Set on Trees

Problem: Given a tree $T = \langle V, E \rangle$ and weights $w: V \to \mathbb{R}_0^+$, find an independent set of maximum total weight.

Algorithm (root $r$, bottom-up):

$B[v]$: maximum weight of an independent set in subtree $T_v$ that does not contain $v$.
$A[v]$: maximum weight of any independent set in $T_v$.

Recurrences:

Leaf: $B[v]=0, A[v]=w(v)$.
Internal node with children $v_1,\dots,v_q$: $$ B[v] = \sum_{i=1}^q A[v_i],\ A[v] = \max\left(B[v],w(v) + \sum_{i=1}^q B[v_i]\right). $$

Solution: $A[r]$.

Running time: $O(n)$.

Weighted Independent Set Parameterized by Path-width

Input: $G = \langle V, E \rangle$, weights $w$, a nice path decomposition of width $k$.

Define for every $i \in [1,r]$ and $S \subseteq B_i$ (with $-\infty$ if not independent):

\[ c[i, S] = \max \left\{ w(\hat{S}) \mid \hat{S} \text{ independent},\; S \subseteq \hat{S} \subseteq \bigcup_{j=1}^i B_j,\; \hat{S} \cap B_i = S \right\}. \]

Recurrences:

$i=1$: $c[1,\emptyset]=0$.
Introduce node $i+1$ (introduces $v$): $$ c[i+1, S] = \begin{cases} c[i, S] & \text{if } v \notin S,\newline c[i, S \setminus {v}] + w(v) & \text{if } v \in S. \end{cases} $$
Forget node $i+1$ (forgets $v$):

\[ c[i+1, S] = \max\{ c[i, S],\; c[i, S \cup \{v\}] \}. \]

Answer: $c[r, \emptyset]$. Time complexity: bag size $\le k+1$, at most $2^{k+1}$ states per step, each step $O(k^2)$, $r = O(n)$. Total $O(2^k \cdot k^{O(1)} \cdot n)$.

Theorem: WEIGHTED INDEPENDENT SET can be solved in $O(2^k \cdot k^{O(1)} \cdot n)$ time for graphs of path-width $k$. The same complexity applies to VERTEX COVER.

Weighted Independent Set Parameterized by Tree-width

Given a nice tree decomposition (root $r$) of width $k$, for each node $t$ and independent set $S \subseteq B_t$:

\[ c[t, S] = \max \left\{ w(\hat{S}) \mid \hat{S} \text{ independent},\; S \subseteq \hat{S} \subseteq V_t,\; \hat{S} \cap B_t = S \right\}, \]

where $V_t = \bigcup_{s \in \text{subtree}(t)} B_s$.

Recurrences:

Leaf $t$: $c[t, \emptyset]=0$.
Introduce node $t$ (child $t'$, introduces $v$): $$ c[t, S] = \begin{cases} c[t', S] & \text{if } v \notin S,\newline c[t', S \setminus {v}] + w(v) & \text{if } v \in S. \end{cases} $$
Forget node $t$ (child $t'$, forgets $v$): $$ c[t, S] = \max{ c[t', S],\; c[t', S \cup {v}] }. $$
Join node $t$ (children $t_1, t_2$, $B_t = B_{t_1} = B_{t_2}$): $$ c[t, S] = c[t_1, S] + c[t_2, S] - w(S), \quad \text{where } w(S)=\sum_{v \in S}w(v). $$

Answer: $c[r, \emptyset]$. Time complexity: $|T| = O(k n)$, states per node $\le 2^{k+1}$, $O(k)$ per transition $\Rightarrow$ total $O(2^k \cdot k^{O(1)} \cdot n)$.

Theorem: For graphs of tree-width $k$, WEIGHTED INDEPENDENT SET and VERTEX COVER can be solved in $O(2^k \cdot k^{O(1)} \cdot n)$ time.

General dynamic programming strategy (for tree-width): 1. Formulate a family of properties defined on subtrees such that the global solution can be derived from the properties at the root. 2. Derive recursive equations for each node type (leaf, introduce, forget, join) relating properties of a node to those of its children. 3. Prove correctness (usually two inequalities per node type). 4. Estimate computation time per node in terms of $n$ and $k$. 5. Sum over all nodes; add time to extract solution from the root properties.

Further FPT Results Using Tree-width

Using dynamic programming on tree decompositions, many classical problems become FPT when parameterized by tree-width $k$:

VERTEX COVER, INDEPENDENT SET: $O(2^k \cdot k^{O(1)} \cdot n)$
DOMINATING SET: $O(4^k \cdot k^{O(1)} \cdot n)$
ODD CYCLE TRANSVERSAL: $O(3^k \cdot k^{O(1)} \cdot n)$
MAX CUT: $O(2^k \cdot k^{O(1)} \cdot n)$
$q$-COLORABILITY: $O(q^k \cdot k^{O(1)} \cdot n)$
STEINER TREE, FEEDBACK VERTEX SET, HAMILTONIAN PATH/CYCLE, LONGEST PATH/CYCLE, CHROMATIC NUMBER, CYCLE PACKING, CONNECTED VERTEX COVER, CONNECTED FEEDBACK VERTEX SET: $k^{O(k)} \cdot n$, still in FPT.

Application: Coverage in Multi-Interface Networks (CMI)

Problem CMI($p$): Given $G = \langle V, E \rangle$, available interfaces $W(v) \subseteq \{1,\dots,a\}$ for each $v$, cost $c(i)$ per interface, find $W_A(v) \subseteq W(v)$ with $|W_A(v)| \le p$ such that for every edge $\{u,v\}$, $W_A(u) \cap W_A(v) \neq \emptyset$, minimizing $\sum_{v \in V} \sum_{i \in W_A(v)} c(i)$.

Parameterized complexity (Aloisio & Navarra 2020):

Parameter path-width $k$: CMI(2) solvable in $O(n \cdot (a + \binom{a}{2})^{k+1})$ time.
Parameter carving-width $k$: CMI(2) solvable in $O(n \cdot a^{4k})$ time.
With combined parameter $a + k$, the problem becomes FPT.

Relations Between Width Notions

Using the notion $\kappa_1 \succeq \kappa_2$ (computably bounded above), FPT results transfer upward and hardness results transfer downward. Some known relationships:

$pw(G) \ge tw(G)$ $\Rightarrow$ $pw \succeq tw$
$clw(G) \le 3 \cdot 2^{tw(G)-1}$ $\Rightarrow$ $tw \succeq clw$
$rw(G) \le tw(G)$ $\Rightarrow$ $tw \succeq rw$
$carw(G)$ and $tw(G)$ are not comparable in all classes, but often related.
$cutw(G)$ is related to carving-width, etc.

Summary

Parameter comparison gives formal grounds for transferring algorithmic results.
Path-width and tree-width are central structural parameters that allow efficient dynamic programming for many NP-hard problems.
The dynamic programming follows a standard pattern: define local properties on bags, update according to node types, and solve at the root.
Clique-width is another powerful parameter, intimately linked to MSO logic.
Other width parameters (branch-width, rank-width, carving-width, etc.) enrich the landscape and can be related to tree-width.
Covering problems on multi-interface networks illustrate FPT results using path-width and carving-width.

Overview

Foundations of Parameterized Complexity

Comparing Parameterizations

Notions of Graph Width

Path-width

Tree-width

Clique-width

Other Width Notions via \(f\)-Width

Branch-width

Rank-width

Carving-width and Cut-width

Dynamic Programming Algorithms

Weighted Independent Set on Trees

Weighted Independent Set Parameterized by Path-width

Weighted Independent Set Parameterized by Tree-width

Further FPT Results Using Tree-width

Application: Coverage in Multi-Interface Networks (CMI)

Relations Between Width Notions

Summary