Parameterized algorithms for min-max multiway cut and list digraph homomorphism
Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017), Parameterized algorithms for min-max multiway cut and list digraph homomorphism, Journal of Computer and System Sciences, 86, p. 191-206. 10.1016/j.jcss.2017.01.003
TypeArticle accepté pour publication ou publié
External document linkhttps://hal-lirmm.ccsd.cnrs.fr/lirmm-01487567
Journal nameJournal of Computer and System Sciences
MetadataShow full item record
Author(s)Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sau Valls, Ignasi
Thilikos, Dimitrios M.
Abstract (EN)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. Weparameterize 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)2log `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.
Subjects / KeywordsParameterized complexity; Fixed-Parameter Tractable algorithm; Multiway Cut; Digraph homomorphism
Showing items related by title and author.
Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi (2016) Article accepté pour publication ou publié
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi; Sikdar, Somnath (2013-07) Communication / Conférence