Document Open Access Logo

Parameterized Algorithms for Diverse Multistage Problems

Authors Leon Kellerhals , Malte Renken , Philipp Zschoche

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.55.pdf
  • Filesize: 0.83 MB
  • 17 pages

Document Identifiers

Author Details

Leon Kellerhals
  • Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, Germany
Malte Renken
  • Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, Germany
Philipp Zschoche
  • Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, Germany

Funding

  • Renken, Malte: Supported by the German Research Foundation (DFG), project MATE (NI 369/17).

Acknowledgements

The authors wish to thank Rolf Niedermeier and anonymous reviewers for their careful reading and suggestions of the manuscript. This work was initiated at the research retreat of the Algorithmics and Computational Complexity group of TU Berlin in September 2020 in Zinnowitz.

Cite AsGet BibTex

Leon Kellerhals, Malte Renken, and Philipp Zschoche. Parameterized Algorithms for Diverse Multistage Problems. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.55

Abstract

The world is rarely static - many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the multistage view on computational problems. We study the diverse multistage variant, where consecutive solutions of large variety are preferable to similar ones, e.g. for reasons of fairness or wear minimization. While some aspects of this model have been tackled before, we introduce a framework allowing us to prove that a number of diverse multistage problems are fixed-parameter tractable by diversity, namely Perfect Matching, s-t Path, Matroid Independent Set, and Plurality Voting. This is achieved by first solving special, colored variants of these problems, which might also be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • Temporal graphs
  • dissimilar solutions
  • fixed-parameter tractability
  • perfect matchings
  • s-t paths
  • committee election
  • spanning forests
  • matroids

Metrics

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

Related Versions

References

  1. Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107:108-123, 2020. URL: https://doi.org/10.1016/j.jcss.2019.08.002.
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  3. Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, and Petra Wolf. Diversity in kemeny rank aggregation: A parameterized approach, 2021. URL: http://arxiv.org/abs/2105.09413.
  4. Evripidis Bampis, Bruno Escoffier, and Alexander V. Kononov. LP-based algorithms for multistage minimization problems, 2019. URL: http://arxiv.org/abs/1909.10354.
  5. Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos. Multistage matchings. In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 101, pages 7:1-7:13, 2018. URL: https://doi.org/10.4230/LIPIcs.SWAT.2018.7.
  6. Evripidis Bampis, Bruno Escoffier, Kevin Schewior, and Alexandre Teiller. Online multistage subset maximization problems. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA), volume 144, pages 11:1-11:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.11.
  7. Evripidis Bampis, Bruno Escoffier, and Alexandre Teiller. Multistage knapsack. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 138, pages 22:1-22:14, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.22.
  8. Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond. Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pages 1119-1125, 2020. URL: https://doi.org/10.24963/ijcai.2020/156.
  9. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation, 243:86-111, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.008.
  10. Niclas Boehmer and Rolf Niedermeier. Broadening the research agenda for computational social choice: Multiple preference profiles and multiple solutions. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1-5, 2021. Google Scholar
  11. Robert Bredereck, Till Fluschnik, and Andrzej Kaczmarczyk. Multistage committee election, 2020. URL: http://arxiv.org/abs/2005.02300.
  12. Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding temporal paths under waiting time constraints. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC), volume 181, pages 30:1-30:18, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.30.
  13. Markus Chimani, Niklas Troost, and Tilo Wiedera. Approximating multistage matching problems, 2020. URL: http://arxiv.org/abs/2002.06887.
  14. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  15. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 150-159, 2011. URL: https://doi.org/10.1109/FOCS.2011.23.
  16. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 4th edition, 2010. Google Scholar
  17. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  18. David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 459-470, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_39.
  19. Till Fluschnik. A multistage view on 2-satisfiability. In Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC), 2021. To appear. URL: http://arxiv.org/abs/2011.02325.
  20. Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche. Multistage vertex cover. In Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC), volume 148, pages 14:1-14:14, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.14.
  21. Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche. Multistage s-t path: Confronting similarity with dissimilarity in temporal graphs. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC), volume 181, pages 43:1-43:16, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.43.
  22. Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov. Diverse pairs of matchings. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC), volume 181, pages 26:1-26:12, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.26.
  23. Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Diverse collections in matroids and graphs. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 187, pages 31:1-31:14, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.31.
  24. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Representative sets of product families. In Proceedings of the 22nd Annual European Symposium on Algorithms (ESA), volume 8737, pages 443-454, 2014. URL: https://doi.org/10.1007/978-3-662-44777-2_37.
  25. Anupam Gupta, Kunal Talwar, and Udi Wieder. Changing bases: Multistage optimization for matroids and matchings. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), volume 8572, pages 563-575, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_47.
  26. Klaus Heeger, Anne-Sophie Himmel, Frank Kammer, Rolf Niedermeier, Malte Renken, and Andrej Sajenko. Multistage graph problems on a global budget. Theoretical Computer Science, 868:46-64, 2021. URL: https://doi.org/10.1016/j.tcs.2021.04.002.
  27. László Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical Society, 2009. Google Scholar
  28. George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing maximum matchings in temporal graphs. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 154, pages 27:1-27:14, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.27.
  29. George B. Mertzios, Hendrik Molter, and Viktor Zamaraev. Sliding window temporal graph coloring. In Proceedings of the 33rd Conference on Artificial Intelligence (AAAI), pages 7667-7674, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33017667.
  30. Frank Mousset, Andreas Noever, Nemanja Škoric, and Felix Weissenberger. A tight Erdős-Pósa function for long cycles. Journal of Combinatorial Theory Series B, 125:21-32, 2017. URL: https://doi.org/10.1016/j.jctb.2017.01.004.
  31. Thomas Muir. A Treatise on the Theory of Determinants. MacMillan and Co., London, 1882. Google Scholar
  32. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. URL: https://doi.org/10.1007/BF02579206.
  33. Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pages 182-191, 1995. URL: https://doi.org/10.1109/SFCS.1995.492475.
  34. Lino Steinhau. Parameterized algorithmics of multistage matching. Bachelor thesis, Technische Universität Berlin, 2020. Google Scholar
  35. Philipp Zschoche. A faster parameterized algorithm for temporal matching, 2021. URL: http://arxiv.org/abs/2010.10408.
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