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
Type
Article accepté pour publication ou publiéExternal document link
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01487567Date
2017Journal name
Journal of Computer and System SciencesVolume
86Publisher
Elsevier
Pages
191-206
Publication identifier
Metadata
Show full item recordAuthor(s)
Kim, Eun JungLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paul, Christophe
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 / Keywords
Parameterized complexity; Fixed-Parameter Tractable algorithm; Multiway Cut; Digraph homomorphismRelated items
Showing items related by title and author.
-
Kim, Eun Jung; Oum, Sang-il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2018) Article accepté pour publication ou publié
-
Kim, Eun Jung; Oum, Sang-Il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2015) Communication / Conférence
-
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