Constant ratio fixed-parameter approximation of the edge multicut problem |
| |
Authors: | Dá niel Marx,Igor Razgon |
| |
Affiliation: | a Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Hungary b Cork Constraint Computation Centre, University College Cork, Ireland |
| |
Abstract: | The input of the Edge Multicut problem consists of an undirected graph G and pairs of terminals {s1,t1},…,{sm,tm}; the task is to remove a minimum set of edges such that si and ti are disconnected for every 1?i?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)⋅nO(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 the parameterized Max-2SAT 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. |
| |
Keywords: | Fixed-parameter algorithms Parameterized approximation Multicut Satisfiability problems Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|