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

Abstract : In this paper we design {\sf FPT}-algorithms for two parameterized problems. The first is \textsc{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 \textsc{Multiway Cut}, namely \textsc{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 \textsc{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(ℓ⋅logh+ℓ2⋅logℓ)⋅n4⋅logn algorithm, where h is the order of the host graph H. We also prove that \textsc{Min-Max Multiway Cut} can be solved in time 2O((ℓr)2logℓr)⋅n4⋅logn. Our approach introduces a general problem, called {\sc List Allocation}, whose expressive power permits the design of parameterized reductions of both aforementioned problems to it. Then our results are based on an {\sf FPT}-algorithm for the {\sc List Allocation} problem that is designed using a suitable adaptation of the {\em randomized contractions} technique (introduced by [Chitnis, Cygan, Hajiaghayi, Pilipczuk, and Pilipczuk, FOCS 2012]).
Document type :
Reports
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01225570
Contributor : Dimitrios M. Thilikos <>
Submitted on : Friday, November 6, 2015 - 12:16:27 PM
Last modification on : Friday, October 5, 2018 - 9:14:01 PM

Links full text

Identifiers

  • HAL Id : lirmm-01225570, version 1
  • ARXIV : 1509.07404

Collections

Relations

Citation

Kim Eun Jung, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism. [Research Report] LIRMM. 2015. ⟨lirmm-01225570⟩

Share

Metrics

Record views

157