Complexity of stability
From MaRDI portal
Publication:2237893
DOI10.1016/J.JCSS.2021.07.001zbMATH Open1472.68113arXiv1910.00305OpenAlexW3183453945MaRDI QIDQ2237893FDOQ2237893
Authors: Fabian Frei, Edith Hemaspaandra, Jörg Rothe 
Publication date: 28 October 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
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 Theta_2^p, a well-known complexity class in the second level of the polynomial hierarchy, which is also known as "parallel access to NP."
Full work available at URL: https://arxiv.org/abs/1910.00305
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- The complexity of facets resolved
- Social and economic networks.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some Theorems on Abstract Graphs
- The complexity of Kemeny elections
- Some simplified NP-complete graph problems
- A graph coloring algorithm for large scheduling problems
- Domination alteration sets in graphs
- Role colouring a graph
- The complexity of facets (and some facets of complexity)
- More complicated questions about maxima and minima, and some closures of NP
- Bounded Query Classes
- Core stability in hedonic coalition formation
- Exact complexity of the winner problem for Young elections
- Exact analysis of Dodgson elections
- On computing Boolean connectives of characteristic functions
- The strong exponential hierarchy collapses
- Title not available (Why is that?)
- Title not available (Why is that?)
- Determining computational complexity from characteristic ``phase transitions
- Anticritical graphs
- On the complexity of unfrozen problems
- The complexity of online manipulation of sequential elections
- Total domination critical and stable graphs upon edge removal
- Graphs whose vertex independence number is unaffected by single edge addition or deletion
- Extremal graphs domination insensitive to the removal of \(k\) edges
- Total domination stability in graphs
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- Exact complexity of exact-four-colorability
- Structural properties of edge-chromatic critical multigraphs
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
- Finding Optimal Solutions With Neighborly Help.
- Title not available (Why is that?)
- Complexity of Stability.
Cited In (2)
This page was built for publication: Complexity of stability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2237893)
