Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism

Eun Jung Kim Christophe Paul 1 Ignasi Sau 1 Dimitrios M. Thilikos 1, 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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. We parameterize 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 2 O(·log h+ 2 ·log) · n 4 · 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 2 O((r) 2 log 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 FPT-algorithm 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]).
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01263999
Contributor : Christophe Paul <>
Submitted on : Thursday, November 15, 2018 - 6:48:51 PM
Last modification on : Thursday, November 15, 2018 - 6:52:02 PM

File

10.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism. IPEC: International symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. pp.78-89, ⟨10.4230/LIPIcs.IPEC.2015.78⟩. ⟨lirmm-01263999⟩

Share

Metrics

Record views

102

Files downloads

46