zbMATH — the first resource for mathematics

Constant ratio fixed-parameter approximation of the edge multicut problem. (English) Zbl 1256.68163
Fiat, Amos (ed.) et al., Algorithms – ESA 2009. 17th annual European symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04127-3/pbk). Lecture Notes in Computer Science 5757, 647-658 (2009).
Summary: The input of the Edge Multicut problem consists of an undirected graph \(G\) and pairs of terminals \(\{s _{1},t _{1}\}, \dots , \{s _{m },t _{m }\}\); the task is to remove a minimum set of edges such that \(s _{i }\) and \(t _{i }\) are disconnected for every \(1 \leq i \leq m\). The parameterized complexity of the problem, parameterized by the maximum number \(k\) of edges that are allowed to be removed, is currently open. The main result of the paper is a parameterized 2-approximation algorithm: in time \(f(k)\cdot n ^{O(1)}\), we can either find a solution of size \(2k\) or correctly conclude that there is no solution of size \(k\).
The proposed algorithm is based on a transformation of the Edge Multicut problem into a variant of parameterized Max-2-SAT problem, where the parameter is related to the number of clauses that are not satisfied. It follows from previous results that the latter problem can be 2-approximated in a fixed-parameter time; on the other hand, we show here that it is W[1]-hard. Thus the additional contribution of the present paper is introducing the first natural W[1]-hard problem that is constant-ratio fixed-parameter approximable.
For the entire collection see [Zbl 1173.68009].

68W25 Approximation algorithms
05C40 Connectivity
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI