Abstract
In this paper we design FPTalgorithms 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 MinMax Multiway Cut: given a graph G, a nonnegative integer l, 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 l 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 nonloop edges of H and we give a time 2^{O(l * log(h) + l^{2 * log(l)}} * n^{4} * log(n) algorithm, where h is the order of the host graph H.We also prove that MinMax Multiway Cut can be solved in time 2^{O((l * r)^2 * log(l *r))} * n^{4} * 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 FPTalgorithm 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]).
BibTeX  Entry
@InProceedings{kim_et_al:LIPIcs:2015:5573,
author = {Eun Jung Kim and Christophe Paul and Ignasi Sau and Dimitrios M. Thilikos},
title = {{Parameterized Algorithms for MinMax Multiway Cut and List Digraph Homomorphism}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {7889},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897927},
ISSN = {18688969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5573},
URN = {urn:nbn:de:0030drops55738},
doi = {10.4230/LIPIcs.IPEC.2015.78},
annote = {Keywords: Parameterized complexity, FixedParameter Tractable algorithm, Multiway Cut, Digraph homomorphism}
}
Keywords: 

Parameterized complexity, FixedParameter Tractable algorithm, Multiway Cut, Digraph homomorphism 
Collection: 

10th International Symposium on Parameterized and Exact Computation (IPEC 2015) 
Issue Date: 

2015 
Date of publication: 

19.11.2015 