Show simple item record

Parameterized algorithms for min-max multiway cut and list digraph homomorphism

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung
hal.structure.identifier
dc.contributor.authorPaul, Christophe
HAL ID: 4726
hal.structure.identifier
dc.contributor.authorSau Valls, Ignasi
HAL ID: 7331
ORCID: 0000-0002-8981-9287
hal.structure.identifier
dc.contributor.authorThilikos, Dimitrios M.
HAL ID: 178742
ORCID: 0000-0003-0470-1800
dc.date.accessioned2020-05-27T12:53:25Z
dc.date.available2020-05-27T12:53:25Z
dc.date.issued2017
dc.identifier.issn0022-0000
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20785
dc.language.isoenen
dc.subjectParameterized complexityen
dc.subjectFixed-Parameter Tractable algorithmen
dc.subjectMultiway Cuten
dc.subjectDigraph homomorphismen
dc.subject.ddc511en
dc.titleParameterized algorithms for min-max multiway cut and list digraph homomorphismen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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.isversionofjnlnameJournal of Computer and System Sciences
dc.relation.isversionofjnlvol86en
dc.relation.isversionofjnldate2017
dc.relation.isversionofjnlpages191-206en
dc.relation.isversionofdoi10.1016/j.jcss.2017.01.003en
dc.identifier.urlsitehttps://hal-lirmm.ccsd.cnrs.fr/lirmm-01487567en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-05-27T12:46:47Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record