Back to Search
Start Over
Parameterized algorithms for min-max multiway cut and list digraph homomorphism.
- Source :
-
Journal of Computer & System Sciences . Jun2017, Vol. 86, p191-206. 16p. - Publication Year :
- 2017
-
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 ( ℓ ⋅ 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]
- Subjects :
- *HOMOMORPHISMS
*PARAMETERIZATION
*DIRECTED graphs
*ALGORITHMS
*PARTITION functions
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 86
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 121454992
- Full Text :
- https://doi.org/10.1016/j.jcss.2017.01.003