On Algorithms Employing Treewidth for $L$-bounded Cut Problems

Petr Kolman

Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 177-191.

Résumé

Given a graph $G=(V,E)$ with two distinguished vertices $s,t\in V$ and an integer parameter $L>0$, an $L$-bounded cut is a subset $F$ of edges (vertices) such that the every path between $s$ and $t$ in $G\setminus F$ has length more than $L$. The task is to find an $L$-bounded cut of minimum cardinality. Though the problem is very simple to state and has been studied since the beginning of the 70's, it is not much understood yet. The problem is known to be $\cal{NP}$-hard to approximate within a small constant factor even for $L\geq 4$ (for $L\geq 5$ for the vertex-deletion version). On the other hand, the best known approximation algorithm for general graphs has approximation ratio only $\mathcal{O}({n^{2/3}})$ in the edge case, and $\mathcal{O}({\sqrt{n}})$ in the vertex case, where $n$ denotes the number of vertices. We show that for planar graphs, it is possible to solve both the edge- and the vertex-deletion version of the problem optimally in $\mathcal{O}((L+2)^{3L}n)$ time. That is, the problem is fixed-parameter tractable (FPT) with respect to $L$ on planar graphs. Furthermore, we show that the problem remains FPT even for bounded genus graphs, a super class of planar graphs. Our second contribution deals with approximations of the vertex-deletion version of the problem. We describe an algorithm that for a given graph $G$, its tree decomposition of width $\tau$ and vertices $s$ and $t$ computes a $\tau$-approximation of the minimum $L$-bounded $s-t$ vertex cut; if the decomposition is not given, then the approximation ratio is $\mathcal{O}(\tau \sqrt{\log \tau})$. For graphs with treewidth bounded by $\mathcal{O}(n^{1/2-\epsilon})$ for any $\epsilon>0$, but not by a constant, this is the best approximation in terms of $n$ that we are aware of.

Détail

DOI : 10.7155/jgaa.00462