License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2022.16
URN: urn:nbn:de:0030-drops-159587
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15958/
Go to the corresponding LIPIcs Volume Portal

Fluschnik, Till ; Kunz, Pascal

Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring

pdf-format:
LIPIcs-SAND-2022-16.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{fluschnik_et_al:LIPIcs.SAND.2022.16,
  author =	{Fluschnik, Till and Kunz, Pascal},
  title =	{{Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15958},
  URN =		{urn:nbn:de:0030-drops-159587},
  doi =		{10.4230/LIPIcs.SAND.2022.16},
  annote =	{Keywords: structural parameters, NP-hardness, parameterized algorithms, multistage problems}
}

Keywords: structural parameters, NP-hardness, parameterized algorithms, multistage problems
Collection: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Issue Date: 2022
Date of publication: 29.04.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI