Complexity of stability
From MaRDI portal
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."
Recommendations
Cites work
- scientific article; zbMATH DE number 3166040 (Why is no real title available?)
- scientific article; zbMATH DE number 3908468 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- scientific article; zbMATH DE number 2080215 (Why is no real title available?)
- scientific article; zbMATH DE number 3290993 (Why is no real title available?)
- A graph coloring algorithm for large scheduling problems
- Anticritical graphs
- Bounded Query Classes
- Complexity of Stability.
- Core stability in hedonic coalition formation
- Determining computational complexity from characteristic ``phase transitions
- Domination alteration sets in graphs
- Exact analysis of Dodgson elections
- Exact complexity of exact-four-colorability
- Exact complexity of the winner problem for Young elections
- Extremal graphs domination insensitive to the removal of k edges
- Finding Optimal Solutions With Neighborly Help.
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
- Graphs whose vertex independence number is unaffected by single edge addition or deletion
- More complicated questions about maxima and minima, and some closures of NP
- On computing Boolean connectives of characteristic functions
- On the complexity of unfrozen problems
- Role colouring a graph
- Social and economic networks.
- Some Theorems on Abstract Graphs
- Some simplified NP-complete graph problems
- Structural properties of edge-chromatic critical multigraphs
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- The complexity of Kemeny elections
- The complexity of facets (and some facets of complexity)
- The complexity of facets resolved
- The complexity of online manipulation of sequential elections
- The strong exponential hierarchy collapses
- Total domination critical and stable graphs upon edge removal
- Total domination stability in graphs
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)
