TY - GEN

T1 - Parameterized algorithms for Min-Max Multiway cut and list digraph homomorphism

AU - Kim, Eunjung

AU - Paul, Christophe

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© Eunjung Kim, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos;.

PY - 2015/11/1

Y1 - 2015/11/1

N2 - In this paper we design FPT-algorithms for two parameterized problems. The first is List Digraph Homomorphism: given two digraphs G and H and a list of allowed vertices of H for every vertex of G, the question is whether there exists a homomorphism from G to H respecting the list constraints. The second problem is a variant of Multiway Cut, namely Min-Max Multiway Cut: given a graph G, a non-negative integer ℓ, and a set T of r terminals, the question is whether we can partition the vertices of G into r parts such that (a) each part contains one terminal and (b) there are at most ℓ edges with only one endpoint in this part. We parameterize List Digraph Homomorphism by the number w of edges of G that are mapped to non-loop edges of H and we give a time 2O(ℓ·log h+ℓ2·log ℓ) · n4 · log n algorithm, where h is the order of the host graph H. We also prove that Min-Max Multiway Cut can be solved in time 2O((ℓr)2 log ℓr) · n4 · log n. Our approach introduces a general problem, called List Allocation, whose expressive power permits the design of parameterized reductions of both aforementioned problems to it. Then our results are based on an FPT-algorithm for the List Allocation problem that is designed using a suitable adaptation of the randomized contractions technique (introduced by [Chitnis, Cygan, Hajiaghayi, Pilipczuk, and Pilipczuk, FOCS 2012]).

AB - In this paper we design FPT-algorithms for two parameterized problems. The first is List Digraph Homomorphism: given two digraphs G and H and a list of allowed vertices of H for every vertex of G, the question is whether there exists a homomorphism from G to H respecting the list constraints. The second problem is a variant of Multiway Cut, namely Min-Max Multiway Cut: given a graph G, a non-negative integer ℓ, and a set T of r terminals, the question is whether we can partition the vertices of G into r parts such that (a) each part contains one terminal and (b) there are at most ℓ edges with only one endpoint in this part. We parameterize List Digraph Homomorphism by the number w of edges of G that are mapped to non-loop edges of H and we give a time 2O(ℓ·log h+ℓ2·log ℓ) · n4 · log n algorithm, where h is the order of the host graph H. We also prove that Min-Max Multiway Cut can be solved in time 2O((ℓr)2 log ℓr) · n4 · log n. Our approach introduces a general problem, called List Allocation, whose expressive power permits the design of parameterized reductions of both aforementioned problems to it. Then our results are based on an FPT-algorithm for the List Allocation problem that is designed using a suitable adaptation of the randomized contractions technique (introduced by [Chitnis, Cygan, Hajiaghayi, Pilipczuk, and Pilipczuk, FOCS 2012]).

KW - Digraph homomorphism

KW - Fixed-Parameter Tractable algorithm

KW - Multiway Cut

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=84958247255&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958247255&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2015.78

DO - 10.4230/LIPIcs.IPEC.2015.78

M3 - Conference contribution

AN - SCOPUS:84958247255

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 78

EP - 89

BT - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015

A2 - Husfeldt, Thore

A2 - Husfeldt, Thore

A2 - Kanj, Iyad

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015

Y2 - 16 September 2015 through 18 September 2015

ER -