Abstract
We consider the problems Zero Extension and Metric Labelling under the paradigm of parameterized complexity. These are natural, wellstudied 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 FPTalgorithms: 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^{qp} Tm + Tphi(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 maxflow 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:194:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9098},
URN = {urn:nbn:de:0030drops90989},
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 