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

Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


We design FPT-algorithms for the following problems. The first is LIST DIGRAPH HOMOMORPHISM: given two digraphs G and H, with order n and h, respectively, and a list of allowed vertices of H for every vertex of G, does there exist a homomorphism from G to H respecting the list constraints? Let ℓ be the number of edges of G mapped to non-loop edges of H. The second problem is MIN-MAX MULTIWAY CUT: given a graph G, an integer ℓ≥0, and a set T of r terminals, can we partition V(G) into r parts such that each part contains one terminal and there are at most ℓ edges with only one endpoint in this part? We solve both problems in time 2O(ℓ⋅log⁡h+ℓ2⋅log⁡ℓ)⋅n4⋅log⁡n and 2O((ℓr)2log⁡ℓr)⋅n4⋅log⁡n, respectively, via a reduction to a new problem called LIST ALLOCATION, which we solve adapting the randomized contractions technique of Chitnis et al. (2012) [4].

Original languageEnglish (US)
Pages (from-to)191-206
Number of pages16
JournalJournal of Computer and System Sciences
StatePublished - Jun 1 2017


  • Digraph homomorphism
  • Fixed-Parameter Tractable algorithm
  • Multiway Cut
  • Parameterized complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Parameterized algorithms for min-max multiway cut and list digraph homomorphism'. Together they form a unique fingerprint.

Cite this