License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.19
URN: urn:nbn:de:0030-drops-133631
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13363/
Go to the corresponding LIPIcs Volume Portal

Frei, Fabian ; Hemaspaandra, Edith ; Rothe, Jörg

Complexity of Stability

pdf-format:
LIPIcs-ISAAC-2020-19.pdf (0.5 MB)

Abstract

Graph parameters such as the clique number, the chromatic number, and the independence number are central in many areas, ranging from computer networks to linguistics to computational neuroscience to social networks. In particular, the chromatic number of a graph (i.e., the smallest number of colors needed to color all vertices such that no two adjacent vertices are of the same color) can be applied in solving practical tasks as diverse as pattern matching, scheduling jobs to machines, allocating registers in compiler optimization, and even solving Sudoku puzzles. Typically, however, the underlying graphs are subject to (often minor) changes. To make these applications of graph parameters robust, it is important to know which graphs are stable for them in the sense that adding or deleting single edges or vertices does not change them. We initiate the study of stability of graphs for such parameters in terms of their computational complexity. We show that, for various central graph parameters, the problem of determining whether or not a given graph is stable is complete for Θ₂ᵖ, a well-known complexity class in the second level of the polynomial hierarchy, which is also known as "parallel access to NP."

BibTeX - Entry

@InProceedings{frei_et_al:LIPIcs:2020:13363,
  author =	{Fabian Frei and Edith Hemaspaandra and J{\"o}rg Rothe},
  title =	{{Complexity of Stability}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13363},
  URN =		{urn:nbn:de:0030-drops-133631},
  doi =		{10.4230/LIPIcs.ISAAC.2020.19},
  annote =	{Keywords: Stability, Robustness, Complexity, Local Modifications, Colorability, Vertex Cover, Clique, Independent Set, Satisfiability, Unfrozenness, Criticality, DP, coDP, Parallel Access to NP}
}

Keywords: Stability, Robustness, Complexity, Local Modifications, Colorability, Vertex Cover, Clique, Independent Set, Satisfiability, Unfrozenness, Criticality, DP, coDP, Parallel Access to NP
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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