dc.contributor.author Kim, Eun Jung dc.contributor.author Paul, Christophe dc.contributor.author Sau Valls, Ignasi dc.contributor.author Thilikos, Dimitrios M. dc.date.accessioned 2020-05-27T12:53:25Z dc.date.available 2020-05-27T12:53:25Z dc.date.issued 2017 dc.identifier.issn 0022-0000 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/20785 dc.language.iso en en dc.subject Parameterized complexity en dc.subject Fixed-Parameter Tractable algorithm en dc.subject Multiway Cut en dc.subject Digraph homomorphism en dc.subject.ddc 511 en dc.title Parameterized algorithms for min-max multiway cut and list digraph homomorphism en dc.type Article accepté pour publication ou publié dc.description.abstracten 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. en dc.relation.isversionofjnlname Journal of Computer and System Sciences dc.relation.isversionofjnlvol 86 en dc.relation.isversionofjnldate 2017 dc.relation.isversionofjnlpages 191-206 en dc.relation.isversionofdoi 10.1016/j.jcss.2017.01.003 en dc.identifier.urlsite https://hal-lirmm.ccsd.cnrs.fr/lirmm-01487567 en dc.relation.isversionofjnlpublisher Elsevier en dc.subject.ddclabel Principes généraux des mathématiques en dc.relation.forthcoming non en dc.relation.forthcomingprint non en dc.description.ssrncandidate non en dc.description.halcandidate non en dc.description.readership recherche en dc.description.audience International en dc.relation.Isversionofjnlpeerreviewed oui en dc.relation.Isversionofjnlpeerreviewed oui en dc.date.updated 2020-05-27T12:46:47Z hal.person.labIds 989 hal.person.labIds hal.person.labIds hal.person.labIds
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.