LIPIcs.SAND.2022.16.pdf
- Filesize: 1.04 MB
- 18 pages
Document
Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring
Authors
Till Fluschnik 
,
Pascal Kunz
-
Part of:
Volume:
1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Algorithmic Foundations of Dynamic Networks (SAND) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-04-29
File
Document Identifiers
Author Details
Cite As Get BibTex
Till Fluschnik and Pascal Kunz. Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.16
Abstract
We consider the algorithmic complexity of recognizing bipartite temporal graphs. Rather than defining these graphs solely by their underlying graph or individual layers, we define a bipartite temporal graph as one in which every layer can be 2-colored in a way that results in few changes between any two consecutive layers. This approach follows the framework of multistage problems that has received a growing amount of attention in recent years. We investigate the complexity of recognizing these graphs. We show that this problem is NP-hard even if there are only two layers or if only one change is allowed between consecutive layers. We consider the parameterized complexity of the problem with respect to several structural graph parameters, which we transfer from the static to the temporal setting in three different ways. Finally, we consider a version of the problem in which we only restrict the total number of changes throughout the lifetime of the graph. We show that this variant is fixed-parameter tractable with respect to the number of changes.
Subject Classification
ACM Subject Classification
- Theory of computation → Fixed parameter tractability
- Theory of computation → Parameterized complexity and exact algorithms
- Theory of computation → Dynamic graph algorithms
Keywords
- structural parameters
- NP-hardness
- parameterized algorithms
- multistage problems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Shorouq Al-Eidi, Yuanzhu Chen, Omar Darwishand, and Ali M. S. Alfosool. Time-ordered bipartite graph for spatio-temporal social network analysis. In Proceedings of the 2020 International Conference on Computing, Networking and Communications (ICNC), pages 833-838, 2020. URL: https://doi.org/10.1109/ICNC47757.2020.9049668.
- Evripidis Bampis, Bruno Escoffier, and Alexander V. Kononov. LP-based algorithms for multistage minimization problems. In Proceedings of the 18th International Workshop on Approximation and Online Algorithms (WAOA), pages 1-15, 2020. URL: https://doi.org/10.1007/978-3-030-80879-2_1.
- 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), pages 7:1-7:13, 2018. URL: https://doi.org/10.4230/LIPIcs.SWAT.2018.7.
- Evripidis Bampis, Bruno Escoffier, and Alexandre Teiller. Multistage knapsack. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 22:1-22:14, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.22.
- Robert Bredereck, Till Fluschnik, and Andrzej Kaczmarczyk. Multistage committee election. arXiv, 2020. URL: http://arxiv.org/abs/2005.02300.
- Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. URL: https://doi.org/10.1016/0020-0190(96)00050-6.
- Markus Chimani, Niklas Troost, and Tilo Wiedera. Approximating multistage matching problems. In Proceedings of the 32nd International Workshop on Combinatorial Algorithms (IWOCA), pages 558-570, 2021. URL: https://doi.org/10.1007/978-3-030-79987-8_39.
- 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.
- Reinhard Diestel. Graph Theory. Springer, 5th edition, 2017. URL: https://doi.org/10.1007/978-3-662-53622-3.
- Michael Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances Rosamond, and Saket Saurabh. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems, 45(4):822-848, 2009. URL: https://doi.org/10.1007/s00224-009-9167-9.
- Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53-61, 2009. URL: https://doi.org/10.1016/j.tcs.2008.09.065.
- Michael R. Fellows, Bart M.P. Jansen, and Frances Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European Journal of Combinatorics, 34(3):541-566, 2013. URL: https://doi.org/10.1016/j.ejc.2012.04.008.
- Till Fluschnik. A multistage view on 2-satisfiability. In Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC), pages 231-244, 2021. URL: https://doi.org/10.1007/978-3-030-75242-2_16.
- Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. As time goes by: Reflections on treewidth for temporal graphs. In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors, Treewidth, Kernels, and Algorithms: Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, pages 49-77. Springer International Publishing, Cham, 2020. URL: https://doi.org/10.1007/978-3-030-42071-0_6.
- Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806:197-218, 2020. URL: https://doi.org/10.1016/j.tcs.2019.03.031.
- 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), pages 14:1-14:14, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.14.
- 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), pages 43:1-43:16, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.43.
- 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), pages 563-575, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_47.
- 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.
- W. A. Horn. Some simple scheduling algorithms. Naval Research Logistics Quarterly, 21(1):177-185, 1974. URL: https://doi.org/10.1002/nav.3800210113.
- Bart M. P. Jansen. The Power of Data Reduction: Kernels for Fundamental Graph Problems. PhD thesis, Utrecht University, 2013. URL: http://dspace.library.uu.nl/handle/1874/276438.
- Leon Kellerhals, Malte Renken, and Philipp Zschoche. Parameterized algorithms for diverse multistage problems. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA), pages 55:1-55:17, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.55.
- Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. Journal of the ACM, 67(3), June 2020. URL: https://doi.org/10.1145/3390887.
- Matthieu Latapy, Clémence Magnien, and Tiphaine Viard. Weighted, bipartite, or directed stream graphs for the modeling of temporal networks. In Petter Holme and Jari Saramäki, editors, Temporal Network Theory, pages 49-64. Springer International Publishing, Cham, 2019. URL: https://doi.org/10.1007/978-3-030-23495-9_3.
- Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms, 11(2):1-31, 2014. URL: https://doi.org/10.1145/2566616.
- Hendrik Molter. Classic Graph Problems Made Temporal: A Parameterized Complexity Analysis. PhD thesis, Technische Universität Berlin, 2020. URL: https://doi.org/10.14279/depositonce-10551.
- Karolina Okrasa and Paweł Rzążewski. Subexponential algorithms for variants of the homomorphism problem in string graphs. Journal of Computer and System Sciences, 109:126-144, 2020. URL: https://doi.org/10.1016/j.jcss.2019.12.004.
- Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences, 67(4):757-771, 2003. URL: https://doi.org/10.1016/S0022-0000(03)00078-3.
- Igor Razgon and Barry O'Sullivan. Almost 2-SAT is fixed-parameter tractable. Journal of Computer and System Sciences, 75(8):435-450, 2009. URL: https://doi.org/10.1016/j.jcss.2009.04.002.
- Róbert Sasák. Comparing 17 graph parameters. Master’s thesis, University of Bergen, 2010. URL: https://bora.uib.no/bora-xmlui/handle/1956/4329.
- Johannes Schröder. Comparing graph parameters. Bachelor’s thesis, Technische Universität Berlin, 2019. URL: http://fpt.akt.tu-berlin.de/publications/theses/BA-Schr%F6der.pdf.
- Manuel Sorge and Mathias Weller. The graph parameter hierarchy. Unpublished manuscript, 2019. URL: https://manyu.pro/assets/parameter-hierarchy.pdf.
- Martin Vatshelle. New Width Parameters of Graphs. PhD thesis, University of Bergen, 2012. URL: https://www.ii.uib.no/~martinv/Papers/MartinThesis.pdf.
- Tsunghan Wu, Sheau-Harn Yu, Wanjiun Liao, and Cheng-Shang Chang. Temporal bipartite projection and link prediction for online social networks. In Proceedings of the 2014 IEEE International Conference on Big Data (Big Data), pages 52-59, 2014. URL: https://doi.org/10.1109/BigData.2014.7004444.
- Mihalis Yannakakis. Node- and edge-deletion NP-complete problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 253-264, 1978. URL: https://doi.org/10.1145/800133.804355.