Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951184 | Journal of Computer and System Sciences | 2017 | 16 Pages |
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 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].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos,