A polynomial time algorithm to compute the connected tree-width of a series-parallel graph*

NEW

Problem: Reconstructed conjecture: for finite simple connected graphs $G$ on $n$ vertices, the decision problem

$$\textsc{Connected Treewidth}=\{(G,k): \operatorname{ctw}(G)\le k\}$$

has an XP algorithm, i.e. runs in $O(n^{f(k)})$ time for some computable function $f$.

Here $\operatorname{ctw}(G)$ is the minimum width of a rooted tree-decomposition $(T,\{X_t\},r)$ such that for every node $t$, the subgraph induced by

$$\bigcup_{u\in V(P_{r,t})}X_u$$

is connected, where $P_{r,t}$ is the root-to-$t$ path in $T$. This is the rooted “connected tree-width” used in the cited paper, not the older variant requiring each bag itself to be connected.

Result: The conjecture is true. In fact, there is an algorithm with running time $O(n^{2k+5})$, up to a $k$-dependent factor.

Key local characterization. Let $(T,\{X_t\},r)$ be a rooted tree-decomposition. It is connected iff:

1. $G[X_r]$ is connected; and
2. for every parent-child edge $p t$ of $T$, every connected component of $G[X_t\setminus X_p]$ has a neighbor in $X_p$.

Proof. If the root-to-$p$ union is connected, then adding $X_t$ keeps it connected exactly when every new component of $X_t\setminus X_p$ attaches to the old union. If such a component attaches to an older bag outside $X_p$, the edge-covering and running-intersection axioms force the attachment vertex to lie in $X_p$. The converse is immediate by induction from the root.

Now define a full block to be a pair $(S,C)$, where $C$ is a connected component of $G-S$ and $N_G(C)=S$. A block $(S,C)$ is feasible if there exists a set $B$ such that

$$S\subseteq B\subseteq S\cup C,\qquad |B|\le k+1,\qquad B\cap C\ne\varnothing,$$

every component of $G[B\setminus S]$ has a neighbor in $S$, and for every component $D$ of $G[C\setminus B]$, the smaller full block $(N_G(D),D)$ is feasible.

This recurrence is correct by induction on $|C|$: choosing $B$ gives the root bag of the decomposition of the block, and the components $D$ are handled recursively. Conversely, any valid connected tree-decomposition restricted to $S\cup C$ has such a first bag $B$, and its child subtrees yield exactly the smaller blocks.

Algorithm:

1. Enumerate all subsets $S\subseteq V(G)$ with $|S|\le k+1$, and all components $C$ of $G-S$. Store the full blocks $(N_G(C),C)$.
2. Sort blocks by increasing $|C|$.
3. Compute feasibility using the recurrence above.
4. Accept iff there exists a connected root bag $R\subseteq V(G)$, $|R|\le k+1$, such that every component $C$ of $G-R$ has feasible block $(N_G(C),C)$.

There are $O(n^{k+2})$ blocks and $O(n^{k+1})$ candidate bags per block; each check is polynomial. Thus the total time is $O(n^{2k+5})$. Boundary cases behave correctly: a one-vertex graph has connected treewidth $0$, disconnected nontrivial graphs have no connected rooted decomposition under this definition, and cycles are rejected for $k=1$.

Therefore $\textsc{Connected Treewidth}$ is in XP parameterized by $k$.

Citation: No known published resolution is used here. The conjecture and definition are from Mescoff, Paul, and Thilikos, “A polynomial time algorithm to compute the connected tree-width of a series-parallel graph,” arXiv:2004.00547.