## Abstract

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(ℓ⋅logh+ℓ2⋅logℓ)}⋅n^{4}⋅logn and 2^{O((ℓr)2logℓr)}⋅n^{4}⋅logn, 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 language | English (US) |
---|---|

Pages (from-to) | 191-206 |

Number of pages | 16 |

Journal | Journal of Computer and System Sciences |

Volume | 86 |

DOIs | |

State | Published - Jun 1 2017 |

## Keywords

- 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