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 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].