Connected Treewidth and Connected Graph Searching

Description

We give a constructive proof of the equality between \emph{treewidth} and \emph{connected treewidth}. More precisely, we describe an $O(nk^3)$-time algorithm that, given any $n$-node width-$k$ tree-decomposition of a connected graph $G$, returns a connected tree-decomposition of $G$ of width $\leq k$. The equality between treewidth and connected treewidth finds applications in \emph{graph searching} problems. First, using equality between treewidth and connected treewidth, we prove that the \emph{connected} search number $\cs(G)$ of a connected graph $G$ is at most $\log{n}+1$ times larger than its search number. Second, using our constructive proof of equality between treewidth and connected treewidth, we design an \\$O(\log n\sqrt{\log OPT})$-approximation algorithm for connected search, running in time $O(t(n)+nk^3\log^{3/2}k+m\log n)$ for $n$-node $m$-edge connected graphs of treewidth at most $k$, where $t(n)$ is the time-complexity of the fastest algorithm for approximating the treewidth, up to a factor $O(\sqrt{\log OPT})$.

Abstract

International audience

Additional details