Document Open Access Logo

Parameterized Algorithms for Zero Extension and Metric Labelling Problems

Authors Felix Reidl, Magnus Wahlström

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.94.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Felix Reidl
  • Royal Holloway, University of London, TW20 0EX, UK
Magnus Wahlström
  • Royal Holloway, University of London, TW20 0EX, UK

Funding

Supported by EPSRC grant EP/P007228/1

Cite AsGet BibTex

Felix Reidl and Magnus Wahlström. Parameterized Algorithms for Zero Extension and Metric Labelling Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 94:1-94:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.94

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • FPT
  • VCSP
  • cut problem
  • gap parameter

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. J. Besag. On the statistical analysis of dirty pictures. J. Royal Stat. Soc. Ser. B, pages 259-302, 1986. Google Scholar
  2. J. Chen, Y. Liu, and S. Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 55(1):1-13, 2009. Google Scholar
  3. R. Chitnis, M. Cygan, M. Hajiaghayi, M. Pilipczuk, and M. Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Sci. Comput., 45(4):1171-1229, 2016. Google Scholar
  4. J. Chuzhoy and J. Naor. The hardness of metric labeling. SIAM J. Sci. Comput., 36(5):1376-1386, 2007. Google Scholar
  5. J.C. Culberson and P. Rudnicki. A fast algorithm for constructing trees from distance matrices. Inf. Process. Lett., 30(4):215-220, 1989. Google Scholar
  6. J. Fakcharoenphol, C. Harrelson, S. Rao, and K. Talwar. An improved approximation algorithm for the 0-extension problem. In Proc. of 14th SODA, pages 257-265. SIAM, 2003. Google Scholar
  7. J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. Google Scholar
  8. H. Hirai. The maximum multiflow problems with bounded fractionality. Math. Oper. Res., 39(1):60-104, 2014. Google Scholar
  9. H. Hirai. Discrete convexity and polynomial solvability in minimum 0-extension problems. Math. Program., 155(1-2):1-55, 2016. Google Scholar
  10. H. Hirai and G. Pap. Tree metrics and edge-disjoint S-paths. Math. Program., 147(1-2):81-123, 2014. Google Scholar
  11. Y. Iwata, M. Wahlström, and Y. Yoshida. Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput., 45(4):1377-1411, 2016. Google Scholar
  12. Y. Iwata, Y. Yamaguchi, and Y. Yoshida. Linear-time FPT algorithms via half-integral non-returning A-path packing. CoRR, abs/1704.02700, 2017. Google Scholar
  13. H. Karloff, S. Khot, A. Mehta, and Y. Rabani. On earthmover distance, metric labeling, and 0-extension. SIAM J. Sci. Comput., 39(2):371-387, 2009. Google Scholar
  14. A.V. Karzanov. Minimum 0-extensions of graph metrics. Eur. J. Comb., 19(1):71-101, 1998. Google Scholar
  15. V. Kolmogorov. Submodularity on a tree: Unifying L^♮natural-convex and bisubmodular functions. In Proc. of 36th MFCS, pages 400-411. Springer, 2011. Google Scholar
  16. V. Kolmogorov, A. A. Krokhin, and M. Rolínek. The complexity of general-valued CSPs. SIAM J. Comput., 46(3):1087-1110, 2017. Google Scholar
  17. S. Kratsch and M. Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In Proc. of 53rd FOCS, pages 450-459. IEEE Computer Society, 2012. Google Scholar
  18. L. Lovász. Flats in matroids and geometric graphs. In Proc. of 6th Br. Comb. Conf., Combinatorial Surveys, pages 45-86, 1977. Google Scholar
  19. R. Manokaran, J. Naor, P. Raghavendra, and R. Schwartz. SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling. In Proc. of 40th STOC, pages 11-20, 2008. Google Scholar
  20. D. Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394-406, 2006. Google Scholar
  21. D. Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471-4479, 2009. Google Scholar
  22. D. Marx and I. Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput., 43(2):355-388, 2014. Google Scholar
  23. M. Naor, L.J.Schulman, and A. Srinivasan. Splitters and near-optimal derandomization. In Proc. of 36th FOCS, pages 182-191. IEEE, 1995. Google Scholar
  24. M. Óskarsdóttir, C. Bravo, W. Verbeke, C. Sarraute, B. Baesens, and J. Vanthienen. A comparative study of social network classifiers for predicting churn in the telecommunication industry. In Proc. of 8th ASONAM, pages 1151-1158. IEEE, 2016. Google Scholar
  25. B. Pang and L. Lee. Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. In Proc. of 43rd ACL, pages 115-124. Association for Computational Linguistics, 2005. Google Scholar
  26. J. Picard and H.D. Ratliff. A cut approach to the rectilinear distance facility location problem. Oper. Res., 26(3):422-433, 1978. Google Scholar
  27. Felix Reidl and Magnus Wahlström. Parameterized algorithms for zero extension and metric labelling problems. CoRR, abs/1802.06026, 2018. URL: http://arxiv.org/abs/1802.06026.
  28. A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. Google Scholar
  29. ls[ 2]J. Kleinberg and E. Tardos. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. J. ACM, 49(5):616-639, 2002. Google Scholar
  30. J. Thapper and S. Živný. The complexity of finite-valued CSPs. J. ACM, 63(4):37, 2016. Google Scholar
  31. N. Vikas. A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results. J. Comput. Syst. Sci., 71(4):406-439, 2005. Google Scholar
  32. M. Wahlström. LP-branching algorithms based on biased graphs. In Proc. of 28th SODA, pages 1559-1570. SIAM, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact