# 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].

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