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

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 2 O ( ℓ ⋅ log ⁡ h + ℓ 2 ⋅ log ⁡ ℓ ) ⋅ n 4 ⋅ log ⁡ n and 2 O ( ( ℓ r ) 2 log ⁡ ℓ r ) ⋅ n 4 ⋅ 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] . [ABSTRACT FROM AUTHOR]