License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.94
URN: urn:nbn:de:0030-drops-90989
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9098/
Reidl, Felix ;
Wahlström, Magnus
Parameterized Algorithms for Zero Extension and Metric Labelling Problems
Abstract
We consider the problems Zero Extension and Metric Labelling under the paradigm of parameterized complexity. These are natural, well-studied problems with important applications, but have previously not received much attention from this area.
Depending on the chosen cost function mu, we find that different algorithmic approaches can be applied to design FPT-algorithms: for arbitrary mu we parameterize by the number of edges that cross the cut (not the cost) and show how to solve Zero Extension in time O(|D|^{O(k^2)} n^4 log n) using randomized contractions. We improve this running time with respect to both parameter and input size to O(|D|^{O(k)} m) in the case where mu is a metric. We further show that the problem admits a polynomial sparsifier, that is, a kernel of size O(k^{|D|+1}) that is independent of the metric mu.
With the stronger condition that mu is described by the distances of leaves in a tree, we parameterize by a gap parameter (q - p) between the cost of a true solution q and a `discrete relaxation' p and achieve a running time of O(|D|^{q-p} |T|m + |T|phi(n,m)) where T is the size of the tree over which mu is defined and phi(n,m) is the running time of a max-flow computation. We achieve a similar result for the more general Metric Labelling, while also allowing mu to be the distance metric between an arbitrary subset of nodes in a tree using tools from the theory of VCSPs. We expect the methods used in the latter result to have further applications.
BibTeX - Entry
@InProceedings{reidl_et_al:LIPIcs:2018:9098,
author = {Felix Reidl and Magnus Wahlstr{\"o}m},
title = {{Parameterized Algorithms for Zero Extension and Metric Labelling Problems}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {94:1--94:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9098},
URN = {urn:nbn:de:0030-drops-90989},
doi = {10.4230/LIPIcs.ICALP.2018.94},
annote = {Keywords: FPT, VCSP, cut problem, gap parameter}
}
|
Keywords: |
|
FPT, VCSP, cut problem, gap parameter |
|
Collection: |
|
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.07.2018 |
