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⁴⋅log⁡n and 2^{O((ℓr)2log⁡ℓr)}⋅n⁴⋅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].