=Paper=
{{Paper
|id=Vol-3072/paper20
|storemode=property
|title=Stability of Special Graph Classes
|pdfUrl=https://ceur-ws.org/Vol-3072/paper20.pdf
|volume=Vol-3072
|authors=Robin Weishaupt,Jörge Rothe
|dblpUrl=https://dblp.org/rec/conf/ictcs/WeishauptR21
}}
==Stability of Special Graph Classes==
https://ceur-ws.org/Vol-3072/paper20.pdf
Stability of Special Graph Classes?
Robin Weishaupt and Jörg Rothe
Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany
robin.weishaupt@hhu.de, rothe@hhu.de
Abstract. Frei et al. [6] showed that the problem to decide whether
a graph is stable with respect to some graph parameter under adding
or removing either edges or vertices is Θ2P -complete. They studied the
common graph parameters α (independence number), β (vertex cover
number), ω (clique number), and χ (chromatic number) for certain vari-
ants of the stability problem. We follow their approach and provide a
large number of polynomial-time algorithms solving these problems for
special graph classes, namely for trees, forests, bipartite graphs, and co-
graphs.
Keywords: Computational Complexity · Graph Theory · Stability · Ro-
bustness · Colorability · Vertex Cover · Independent Set
1 Introduction
Frei et al. [6] comprehensively studied the problem of how stable certain cen-
tral graph parameters are when a given graph is slightly modified, i.e., under
operations such as adding or deleting either edges or vertices. Given a graph
parameter ξ (like, e.g., the independence number or the chromatic number),
they formally introduced the problems ξ-Stability, ξ-VertexStability, ξ-
Unfrozenness, and ξ-VertexUnfrozenness and showed that they are, typi-
cally, Θ2P -complete, that is, they are complete for the complexity class known as
“parallel access to NP,” which was introduced by Papadimitriou and Zachos [18]
and intensely studied by, e.g., Wagner [21, 22], Hemaspaandra et al. [8, 10], and
Rothe et al. [20]; see the survey by Hemaspaandra et al. [9]. Θ2P is contained in the
second level of the polynomial hierarchy and contains the problems that can be
solved in polynomial time by an algorithm that accesses its NP oracle in parallel
(i.e., it first computes all its queries and then asks them all at once and accepts
its input depending on the answer vector). Alternatively, Θ2P = PNP[O(log n)] can
be viewed as the class of problems solvable in polynomial time via adaptively
accessing its NP oracle (i.e., computing the next query depending on the answer
to the previous query) logarithmically often (in the input size).
Furthermore, Frei et al. [6] proved that some more specific versions of these
problems, namely k-χ-Stability and k-χ-VertexStability, are NP-complete
?
Copyright © 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
2 R. Weishaupt and J. Rothe
for k = 3 and DP-complete for k ≥ 4, respectively, where DP was introduced by
Papadimitriou and Yannakakis [17] as the class of problems that can be written
as the difference of NP problems.
Overall, the results of Frei et al. [6] indicate that these problems are rather
intractable and there exist no efficient algorithms solving them exactly. Consid-
ering the vast number of real-world applications for these problems mentioned by
Frei et al. [6]—e.g., the design of infrastructure, coloring algorithms for biological
networks [15, 13] or for complex information, social, and economic networks [12],
etc.—these results are rather disappointing and unsatisfying.
This obstacle motivates us to study whether there are scenarios that allow for
efficient solutions to these problems which in general are intractable. Our work
is based on the assumption that most of the real-world applications of stability
of graph parameters do not use arbitrarily complex graphs but may often be
restricted to certain special graph classes. Consequently, our studies show that—
despite the completeness results by Frei et al. [6]—there are tractable solutions
to these problems when one limits the scope of the problem to a special graph
class. We study four different classes of special graphs: trees (T ), forests (F),
bipartite graphs (B), and co-graphs (C). For each such class, we study twelve
different problems:
– stability, vertex-stability, and unfrozenness
– for the four graph parameters α, β, ω, and χ.
In total, we thus obtain the 48 P membership results shown in Table 1,
which gives the theorem, proposition, or corollary corresponding to each such P
result. These results can be useful for real-world applications when knowledge
about the stability, vertex-stability, or unfrozenness of a graph with respect to
a certain graph parameter is required and graphs with such a special structure
may typically occur in this application.
2 Preliminaries
We follow the notation of Frei et al. [6] and briefly collect the relevant notions
here (referring to their paper [6] for further discussion). Let G be the set of
all undirected, simple graphs without loops. For G ∈ G, we denote by V (G)
its vertex set and by E(G) its edge set; by G its complementary graph with
V (G) = V (G) and E(G) = {{v, w} | v, w ∈ V (G) ∧ v 6= w ∧ {v, w} ∈ / E(G)}. For
v ∈ V (G), e ∈ E(G), and e0 ∈ E(G), let G − v, G − e, and G + e0 , respectively,
denote the graphs that result from G by deleting v, deleting e, and adding e0 .
A graph parameter is a map ξ : G → N. We focus on the prominent graph
parameters α (the size of a maximum independent set), β (the size of a minimum
vertex cover), χ (the chromatic number, i.e., the minimum number of colors
needed to color the vertices of a graph so that no two adjacent vertices have the
same color), and ω (the size of a maximum clique).
For a graph parameter ξ, an edge e ∈ E(G) is said to be ξ-stable if ξ(G) =
ξ(G − e), i.e., ξ(G) remains unchanged after e is deleted from G. Otherwise (i.e.,
Stability of Special Graph Classes 3
Table 1. Overview of P results established for the four special graph classes studied in
this paper. E stands for the edge-related problem and V for the vertex-related problem.
T F B C
E Cor. 3 Thm. 7 Cor. 4 Cor. 10
Stability
α V Cor. 3 Thm. 7 Cor. 4 Thm. 17
Unfrozenness Cor. 7 Cor. 7 Cor. 6 Cor. 12
E Cor. 3 Thm. 7 Cor. 4 Cor. 11
Stability
β V Cor. 3 Thm. 7 Cor. 4 Cor. 8
Unfrozenness Cor. 7 Cor. 7 Thm. 12 Cor. 12
E Cor. 3 Thm. 7 Cor. 4 Thm. 19
Stability
ω V Cor. 3 Thm. 7 Cor. 4 Cor. 9
Unfrozenness Prop. 1 Thm. 8 Cor. 5 Cor. 13
E Cor. 3 Thm. 7 Cor. 4 Thm. 18
Stability
χ V Cor. 3 Thm. 7 Cor. 4 Thm. 16
Unfrozenness Prop. 1 Thm. 8 Thm. 11 Thm. 20
if ξ(G) is changed by deleting e), e is said to be ξ-critical. Stability and criticality
are defined analogously for a vertex v ∈ V (G) instead of an edge e ∈ E(G).
A graph is said to be ξ-stable if all its edges are ξ-stable. A graph whose
vertices (instead of edges) are all ξ-stable is said to be ξ-vertex-stable, and ξ-
criticality and ξ-vertex-criticality are defined analogously. Obviously, each edge
and each vertex is either stable or critical, yet a graph might be neither.
Traditionally, the analogous terms for stability or vertex-stability when an
edge or a vertex is added rather than deleted are unfrozenness and vertex-
unfrozenness: They too indicate that a graph parameter does not change by
this operation. And if, however, a graph parameter changes when an edge or
vertex is added (not deleted), the notions analogous to criticality and vertex-
criticality are simply termed frozenness and vertex-frozenness. Again, each edge
and each vertex is either unfrozen or frozen, but a graph might be neither.
For a graph parameter ξ, define ξ-Stability to be the set of ξ-stable graphs;
and analogously so for the sets ξ-VertexStability, ξ-VertexCriticality, ξ-
Unfrozenness, ξ-Frozenness, and ξ-VertexUnfrozenness. These are the
decision problems studied by Frei et al. [6] for general graphs in terms of their
computational complexity. We will study them restricted to the graph classes
mentioned in the introduction, formally defined in the subsections of Section 4.
A graph class J ⊆ G is closed for (induced) subgraphs if for every G ∈ J it
holds that all (induced) subgraphs H of G satisfy H ∈ J .
The notation of perfect graphs was originally introduced by Berge [2] in 1963:
A graph G ∈ G is called perfect if for all induced subgraphs H of G, we have
χ(H) = ω(H). Note that G is also an induced subgraph of itself.
Let P be the class of problems solvable in (deterministic) polynomial time.
For more background on computational complexity (e.g., regarding the complex-
ity classes NP, DP, and Θ2P mentioned in the introduction; note that P ⊆ NP ⊆
4 R. Weishaupt and J. Rothe
DP ⊆ Θ2P by definition), we refer to the textbooks by Papadimitriou [16] and
Rothe [19].
For the sake of self-containment, we here state Gallai’s theorem [7], which is
used to obtain several of our results.
Theorem 1 (Gallai’s theorem). For every graph G ∈ G, it holds that
|V (G)| = α(G) + β(G).
3 General Stability and Unfrozenness Results
In this section, we provide general results that hold for specific graph classes
satisfying special requirements. These results can be used to easily determine for
a given graph class whether some stability or unfrozenness results are tractable.
Theorem 2. Let J ⊆ G be a graph class closed for induced subgraphs, and ξ a
tractable graph parameter for J . Then ξ-VertexStability ∈ P for all G ∈ J .
Proof. Let G ∈ J and compute ξ(G). For all v ∈ V (G), we have G − v ∈
J , since J is closed for induced subgraphs. Hence, for all v ∈ V (G), we can
compute ξ(G − v) efficiently and compare it to ξ(G). If there is no vertex such
that the values differ, G is ξ-vertex-stable. This approach is computable in time
polynomial in |G|, so that ξ-VertexStability ∈ P for all G ∈ J . q
Since every graph class that is closed for subgraphs is also closed for induced
subgraphs, Corollary 1 is a simple consequence of the previous theorem.
Corollary 1. Let J ⊆ G be a graph class closed under subgraphs and ξ a
tractable graph parameter for J . Then ξ-VertexStability ∈ P for all G ∈ J .
The first theorem made a statement related to vertex-stability about graph
classes closed for induced subgraphs. Theorem 3 is related to stability. Due to
space limitations, some proofs of our results (such as the one of Theorem 3) will
be tacitly omitted; they can be found in the technical report [23].
Theorem 3. Let J ⊆ G be a graph class closed under subgraphs and ξ a
tractable graph parameter for J . Then ξ-Stability ∈ P for all G ∈ J .
Some of the special graph classes we study in the next section are perfect,
which is why we now provide some results for perfect graph classes.
Theorem 4. Let G ∈ G be a perfect graph. Then it holds that G is ω-vertex-
stable if and only if G is χ-vertex-stable.
Based on this result, the next corollary follows immediately.
Corollary 2. Let J ⊆ G be a class of perfect graphs. Then, for all graphs in J ,
we have χ-VertexStability = ω-VertexStability.
Stability of Special Graph Classes 5
While the above results are related to the concepts of stability and vertex-
stability, the subsequent two results address the topic of unfrozenness.
Theorem 5. Let J ⊆ G be a graph class closed under complements and sub-
graphs. If α or β is tractable for J , then ω-Unfrozenness ∈ P for all G ∈ J .
Note that this theorem exploits a relation between α- and β-Stability and
ω-Unfrozenness shown in [6, Proposition 5]. The next theorem follows by a
similar approach, but exploits a relation between ω-Stability and α- and β-
Unfrozenness.
Theorem 6. Let J ⊆ G be a graph class closed under complements and sub-
graphs. If ω is tractable for J , then α- and β-Unfrozenness ∈ P for all G ∈ J .
4 Tractability Results for Special Graph Classes
Ahead of our results for the individual graph classes, we provide two observations
which we will use multiple times in upcoming proofs (presented here or in the
technical report [23]).1
Observation 1. χ-VertexStability ⊆ χ-Stability.
Observation 2. Let G ∈ G be a graph. If an edge {u, v} ∈ E(G) is β-critical,
then u and v are β-critical, too.
With these two observations we can now inspect several graph classes. In the
following subsections we study the problems ξ-Stability, ξ-VertexStability,
and ξ-Unfrozenness with ξ ∈ {α, β, ω, χ}, restricted to special graph classes.
Frei et al. [6] showed that for ξ ∈ {α, ω, χ} we have ξ-VertexUnfrozenness =
∅ as well as β-VertexUnfrozenness = {(∅, ∅)}, where (∅, ∅) is the null graph,
i.e., the graph without vertices or edges (which we will not further consider in
this paper). This is why we do not study problems related to vertex-unfrozenness,
as all related questions are already answered.
We start with investigating trees and forests.
4.1 Trees and Forests
We say G ∈ G is a tree (i.e., G ∈ T ) if G has no isolated vertices and no cycles
of length greater than or equal to 3. Furthermore, G is a forest (i.e., G ∈ F) if
there exist trees G1 , . . . , Gn ∈ T such that G = G1 ∪ · · · ∪ Gn . For every tree
G ∈ T , it holds that |E(G)| = |V (G)| − 1 (see, e.g., Bollobás [3]). So, we have
ω(G) = χ(G) = 2 if |V (G)| > 1, and ω(G) = χ(G) = 1 if |V (G)| = 1.
Also, there exists a tractable algorithm to determine α(G) for trees (for
example, as T ⊆ B, we can simply use the algorithm for bipartite graphs from
Observation 4). Thus we can compute β for trees using Gallai’s theorem [7]
1
Note that the second observation is in line with Observation 2 of Frei et al. [6].
6 R. Weishaupt and J. Rothe
(stated as Theorem 1), and all four graph parameters α, β, ω, and χ are tractable
for trees.
Now, let G ∈ F with G = G1 ∪ · · · ∪ P Gn and Gi ∈ T , 1 ≤Pi ≤ n, be
n n
a forest. It is easy to check that α(G) = i=1 α(Gi ), β(G) = i=1 β(Gi ),
ω(G) = max1≤i≤n ω(Gi ), and χ(G) = max1≤i≤n χ(Gi ). Furthermore, it is known
that the class of forests F is closed under subgraphs and induced subgraphs.
From these observations we have the following results.
Theorem 7. Let ξ ∈ {α, β, ω, χ} be a graph parameter. Then the problems ξ-
Stability and ξ-VertexStability are in P for all forests.
With T ⊆ F the next corollary follows immediately.
Corollary 3. For all G ∈ T and ξ ∈ {α, β, ω, χ}, the problems ξ-Stability
and ξ-VertexStability belong to P.
We now focus on the unfrozenness problems. All trees and forests with fewer
than three vertices are trivial to handle (see the technical report [23] for details).
It remains to study trees and forests with at least three vertices.
Proposition 1. Every tree G ∈ T with |V (G)| ≥ 3 is neither ω- nor χ-unfrozen.
Based on this result we can deduce whether forests are ω- or χ-unfrozen. As
forests without edges are empty graphs, we study forests with at least one edge.
Let Pi denote the path with i vertices.
Theorem 8. If F ∈ F contains P2 but no P3 as induced subgraphs, F is ω- and
χ-unfrozen. If F contains P3 as an induced subgraph, F is not ω- nor χ-unfrozen.
α- and β-Unfrozenness are covered in Corollary 7 of the next subsection.
4.2 Bipartite Graphs
G = (V1 ∪ V2 , E) is a bipartite graph if V1 ∩ V2 = ∅ and E ⊆ {{u, v} | u ∈
V1 ∧ v ∈ V2 }. Denote the set of all bipartite graphs by B. We begin with two
simple observations.
Observation 3. Let G ∈ B be a bipartite graph. Then χ(G) = ω(G) = 1 if
E(G) = ∅, and χ(G) = ω(G) = 2 if E(G) 6= ∅.
Consequently, we can efficiently calculate χ and ω for all bipartite graphs.
The proof of the next observation (see [23]) provides a tractable method to
calculate α and β for bipartite graphs by making use of the approaches due to
Hopcroft and Karp [11] and Kőnig [14].
Observation 4. We can calculate α(G) and β(G) efficiently for G ∈ B.
Hence, we can efficiently calculate ξ(G) for every G ∈ B and ξ ∈ {α, β, ω, χ}.
Furthermore, as the class of bipartite graphs is closed under subgraphs and
induced subgraphs, the following corollary follows from Theorem 2.
Stability of Special Graph Classes 7
Corollary 4. For every ξ ∈ {α, β, ω, χ}, the problems ξ-Stability and ξ-
VertexStability are in P for all bipartite graphs.
Next, we discuss approaches for how to decide whether a bipartite graph
is stable. If a bipartite graph G has no edges, it is trivial to handle [23]. For
bipartite graphs with one edge, we have the following simple result.
Proposition 2. Let G be a bipartite graph with |E(G)| = 1. Then G is neither
ξ-stable nor ξ-vertex-stable for ξ ∈ {α, β, ω, χ}.
We now provide results for bipartite graphs with more than one edge.
Proposition 3. Every bipartite graph G with |E(G)| ≥ 2 is χ-stable.
Proof. Let e ∈ E(G) be an arbitrary edge of G. Since E(G − e) 6= ∅, it holds
that χ(G − e) = 2 = χ(G) and, thus, G is χ-stable. q
Furthermore, we can characterize χ-vertex-stability.
Theorem 9. Let G be a bipartite graph with |E(G)| ≥ 2. G is χ-vertex-stable if
and only if for all v ∈ V (G) it holds that deg(v) < |E(G)|.
Proof. Assume G to be χ-vertex-stable. Furthermore, as we assume that
|E(G)| ≥ 2, it holds that χ(G) = 2. Then there cannot exist a vertex v ∈ V (G)
with deg(v) = |E(G)|, as such a vertex would be χ-critical, since χ(G − v) = 1
because of E(G − v) = ∅. For the opposite direction, assume that for all vertices
v ∈ V (G) we have deg(v) < |E(G)|. Hence, no matter what vertex v ∈ V (G) we
remove from G, it always holds that E(G − v) 6= ∅, so χ(G − v) = 2 = χ(G) and,
thus, G is χ-vertex-stable. q
The proof of the following proposition is similar to that of Proposition 3.
Proposition 4. Every bipartite graph G with |E(G)| ≥ 2 is ω-stable.
Proof. For all e ∈ E(G) we have ω(G − e) = 2 = ω(G) as E(G − e) 6= ∅ holds,
such that G is ω-stable. q
Lastly, we can also characterize ω-vertex-stability.
Theorem 10. Let G be a bipartite graph with |E(G)| ≥ 2. G is ω-vertex-stable
if and only if for all v ∈ V (G) it holds that deg(v) < |E(G)|.
Proof. Assume that G is ω-vertex-stable. Consequently, for all v ∈ V (G) it
holds that ω(G − v) = 2 = ω(G). If there is one v ∈ V (G) with deg(v) = |E(G)|,
we have ω(G − v) = 1 as E(G − v) = ∅, a contradiction to G’s ω-vertex-stability.
Contrarily, assume that for all v ∈ V (G) it holds that deg(v) < |E(G)|. Then, for
all v ∈ V (G), it follows that E(G − v) 6= ∅. Consequently, ω(G) = 2 = ω(G − v)
and, hence, G is ω-vertex-stable. q
Besides these (vertex-)stability characterizations for bipartite graphs, we now
address unfrozenness for them.
8 R. Weishaupt and J. Rothe
Theorem 11. Let G be a bipartite graph. G is χ-unfrozen if and only if G
possesses no P3 as an induced subgraph.
Proof. We prove both directions separately. First, assume G is χ-unfrozen but
contains P3 as an induced subgraph. Write V (P3 ) = {v1 , v2 , v3 } and E(P3 ) =
{{v1 , v2 }, {v2 , v3 }} for the corresponding vertices and edges. Then e = {v1 , v3 } ∈
E(G). However, adding e to G we obtain χ(G) = 2 < 3 = χ(G+e), as P3 +e forms
a 3-clique in G, a contradiction to the assumption that G is χ-unfrozen. Next,
assume that G possesses no P3 as an induced subgraph but is not χ-unfrozen.
Hence, there must exist e = {u, v} ∈ E(G) such that χ(G + e) = 3 > 2 = χ(G).
Denote the two disjoint vertex sets of G by V1 ∪ V2 = V (G). Obviously, u ∈ V1
and v ∈ V2 cannot be true, since then χ(G + e) = 2 would hold. Therefore,
without loss of generality, we assume u, v ∈ V1 . Adding e to G must create a
cycle of odd length in G, as cycles of even length as well as paths can be colored
with two colors. Consequently, G + e possesses Cn with n = 2k + 1 ≥ 3, k ∈ N,
as a subgraph. This implies that G must possess P3 as an induced subgraph,
again a contradiction. q
Slightly modifying (the direction from right to left in) the previous proof
yields Corollary 5. This time, adding e to G must create a 3-clique in G.
Corollary 5. G ∈ B is ω-unfrozen if and only if G possesses no P3 as an
induced subgraph.
Both results show that ω- and χ-Unfrozenness belong to P for bipartite
graphs. For the proof of Theorem 12 (see [23]), which establishes the same result
for β-Unfrozenness, we need the following lemma.
Lemma 1. Let G be a bipartite graph and u ∈ V (G). If β(G − u) = β(G) − 1,
then there exists some vertex cover V 0 ⊆ V (G) with u ∈ V 0 and |V 0 | = β(G).
Theorem 12. For every G ∈ B, the problem β-Unfrozenness belongs to P.
The proof of Theorem 12 allows for every nonedge of a bipartite graph to
decide if it is β-unfrozen, so β-Frozenness is in P for bipartite graphs. By
Gallai’s theorem [7], α-Unfrozenness is in P for bipartite graphs as well.
Corollary 6. For all G ∈ B, α-Unfrozenness and β-Frozenness are in P.
Finally, the next corollary follows by T ⊆ F ⊆ B.
Corollary 7. The problems α- and β-Unfrozenness as well as the problem
β-Frozenness belong to P for all trees and forests.
4.3 Co-Graphs
First of all, we recursively define co-graphs, following a slightly adjusted defini-
tion by Corneil et al. [4].
Stability of Special Graph Classes 9
+
∪ ∪
v1 v3 v2 v4
Fig. 1. Co-tree for C4 .
Definition 1 (co-graph). The graph G = ({v}, ∅) is a co-graph. If G1 and G2
are co-graphs, then G1 ∪ G2 and G1 + G2 are co-graphs, too.
We denote the set of all co-graphs by C and use the operators ∪ and + as is
common (see, e.g., [6]). We will use the following result by Corneil et al. [4].
Theorem 13. Co-graphs are (i) closed under complements and (ii) closed under
induced subgraphs, but (iii) not closed under subgraphs in general. Furthermore,
G ∈ G is a co-graph if and only if G possesses no P4 as an induced subgraph.
Property (iii) is not proven in their work [4]. However, C4 ∈ C is an easy
example since C4 is a co-graph (see Example 1 below), and removing one edge
yields P4 . Since every co-graph can be constructed by ∪ and +, we can identify
a co-graph by its co-expression.
Example 1 (co-expression). The co-expression X = (v1 ∪v3 )+(v2 ∪v4 ) describes
the graph C4 = ({v1 , v2 , v3 , v4 }, {{v1 , v2 }, {v2 , v3 }, {v3 , v4 }, {v4 , v1 }}).
Obviously, we can build a binary tree for every co-graph via its co-expression.
The tree’s leaves correspond to the graph’s vertices and the inner nodes of the
tree correspond to the expression’s operations. For example, the tree in Figure 1
corresponds to the co-expression from Example 1 and, thus, describes a C4 .
Such a tree is called a co-tree. To formulate our results regarding stability and
unfrozenness of co-graphs, we need the following result of Corneil et al. [5].
Theorem 14. For every graph G ∈ G, we can decide in O(|V (G)| + |E(G)|)
time whether G is a co-graph and, if so, provide a corresponding co-tree.
Combining the previous results with the next one by Corneil et al. [4], we
can efficiently determine a co-graph’s chromatic number.
Theorem 15. Let G ∈ G be a co-graph and T the corresponding co-tree. For a
node w from T , denote by G[w] the graph induced by the subtree of T with root w.
To every leave v of T we add as a label χ(G[v]) = 1. For every inner node w of
T we add, depending on the inner node’s type, the following label: (1) If w is a
∪-node with children v1 and v2 , χ(G[w]) = max{χ(G[v1 ]), χ(G[v2 ])}, and (2) if
w is a +-node with children v1 and v2 , χ(G[w]) = χ(G[v1 ]) + χ(G[v2 ]). If r is
the root node of T , then it holds that χ(G[r]) = χ(G).
10 R. Weishaupt and J. Rothe
A result similar to the previous one for α was given by Corneil et al. [4].
Remark 1. We label all leaves of T with α(G[v]) = 1. Each inner node w of T
with children v1 and v2 is labeled by α(G[w]) = max{α(G[v1 ]), α(G[v2 ])} if w
contains the +-operation, and by α(G[w]) = α(G[v1 ]) + α(G[v2 ]) if w contains
the ∪-operation. For the root r of T , it then holds that α(G[r]) = α(G).
By the previous remark we can efficiently calculate α for co-graphs. Based
on these results, we can state the following theorems.
Theorem 16. For every G ∈ C, the problem χ-VertexStability is in P.
With a similar proof as for the previous theorem, we obtain the next result.
Theorem 17. For every G ∈ C, the problem α-VertexStability is in P.
We can use the same proof as for Theorem 17 to obtain the next corollary.
However, this time we additionally use Gallai’s theorem [7] to calculate β out of
α for G and all induced subgraphs with one vertex removed.
Corollary 8. For every co-graph, the problem β-VertexStability is in P.
Now, the subsequent corollary follows with Proposition 5(5) by Frei et al. [6]
because α-VertexStability = {G | G ∈ ω-VertexStability} is true and
co-graphs are closed under complements.
Corollary 9. For all G ∈ C, the problem ω-VertexStability is in P.
Next, let us study the edge-related stability problems for co-graphs. To obtain
our results, we need the following two auxiliary propositions.
Proposition 5. Let G ∈ C with |V (G)| > 1 and let u ∈ V (G) be χ-critical
for G. There exist two co-graphs G1 , G2 such that G = G1 ∪ G2 or G = G1 + G2 .
Assuming, without loss of generality, that u ∈ V (G1 ), u is χ-critical for G1 .
Proposition 6. Let G ∈ C and e = {u, v} ∈ E(G). If u and v are χ-critical
for G, then e is χ-critical for G as well.
Proof. Let G ∈ C be a co-graph and e = {u, v} ∈ E(G) an edge with two
χ-critical vertices u, v ∈ V (G). First, we study the case that G = G1 +G2 as well
as u ∈ V (G1 ) and v ∈ V (G2 ) holds. Afterwards, we explain how to generalize
the proof.
From the previous Proposition 5 we know that u must be χ-critical for G1 and
v χ-critical for G2 . According to Observation 4 from [6] there exists an optimal
coloring c1 : V (G1 ) → N for G1 , such that for all ũ ∈ V (G1 ) \ {u} it holds that
c1 (ũ) 6= c1 (u). In other words, there is a coloring c1 for G1 , such that u is the
only vertex in G1 of its color. A similar, optimal coloring c2 must exist for G2
with respect to v. For the combined graph with e removed, i.e., G − e, according
to Observation 1 from [6], it must hold that χ(G − e) ∈ {χ(G) − 1, χ(G)}.
Consequently, we can reuse c1 and c2 from G1 and G2 , assuming distinct colors
sets for c1 and c2 , to obtain a legal coloring of G with χ(G) colors. However,
we can color u in the same color c2 (v), as v is colored, and thus obtain a legal
coloring for G − e with χ(G) − 1 colors. This is possible because
Stability of Special Graph Classes 11
1. u is the only vertex in G1 colored in c1 (u) by definition of c1 ,
2. no vertex ũ ∈ V (G1 )\{u} is colored with c2 (v), as c1 (V (G1 ))∩c2 (V (G2 )) = ∅
holds, and
3. v is the only vertex in G2 with this color, by definition of c2 , and there is no
edge between u and v.
Consequently, after removing e from G, we can color G − e with one color less
than before, such that χ(G − e) = χ(G) − 1 holds and e is χ-critical.
Initially, we assumed that G = G1 + G2 with u ∈ V (G1 ) and v ∈ V (G2 )
holds. If G = G1 ∪ G2 , there cannot exist any edge between vertices from G1
and G2 . Hence, the only cases left are G = G1 + G2 or G = G1 ∪ G2 with both
vertices in G1 or G2 . Without loss of generality, let us assume that both vertices
are in G1 . Following Proposition 5, we know that both vertices are χ-critical for
G1 , as they are χ-critical for G. When we can show that e is χ-critical for G1 , it
immediately follows that e is also χ-critical for G. That is because if G = G1 +G2
and e is χ-critical for G1 , we have χ(G1 − e) = χ(G1 ) − 1, such that
χ(G − e) = χ(G1 − e) + χ(G2 ) = χ(G1 ) − 1 + χ(G2 ) = χ(G) − 1
holds. If G = G1 ∪ G2 , there is one more argument to add. We know that u
and v are χ-critical for G and G1 . Consequently, χ(G1 ) > χ(G2 ) must hold, as
otherwise, u or v cannot be χ-critical for G, since χ(G) = max{χ(G1 ), χ(G2 )}
is true. But then, it is enough to show that e is χ-critical for G1 , since reducing
χ(G1 ) by one via removing e also causes a reduction of χ(G) by one and hence,
e is χ-critical for G, too.
At some point, we must arrive in the case that one vertex is in G1 and the
other vertex is in G2 and G = G1 + G2 holds, since the +-operation is the only
possibility to add edges between vertices in co-graphs. q
Having these results, we are now able to provide our stability-related results.
Theorem 18. For all co-graphs, the problem χ-Stability is in P.
Proof. Let G ∈ C be a co-graph. We can compute χ(G) efficiently and, accord-
ing to Observation 1 in [6], for every edge e ∈ E(G) and every vertex v ∈ V (G) it
holds that χ(G−e), χ(G−v) ∈ {χ(G)−1, χ(G)}. Thus, for every edge e ∈ E(G),
we proceed as follows to efficiently determine whether e is χ-critical or -stable
for G: Denote e = {u, v} for u, v ∈ V (G). Then it follows that G − u and G − v
are induced subgraphs of G − e and G − e is a subgraph of G. According to the
earlier referenced Observation 1, it must hold that
χ(G − v), χ(G − u) ≤ χ(G − e) ≤ χ(G).
| {z }
∈{χ(G)−1,χ(G)}
Hence, if χ(G−v) = χ(G) or χ(G−u) = χ(G), which we can compute efficiently,
it immediately follows that χ(G−e) = χ(G). In other words, if u or v is χ-stable,
we know that e must be χ-stable, too.2 If u and v are χ-critical, it follows by
2
This is in line with Observation 3 from [6].
12 R. Weishaupt and J. Rothe
Proposition 6 that e is χ-critical. Since we can determine for every node in V (G)
efficiently, whether it is χ-stable, we can also efficiently determine for every edge
in E(G) whether it is χ-stable. Consequently, we can decide in polynomial time
whether G is χ-stable. Thus χ-Stability ∈ P for co-graphs follows. q
Next, we want to study the problem of ω-Stability for co-graphs. To do so,
we need the following lemmas.
Lemma 2. Let G ∈ C be a co-graph. We can compute all cliques of size ω(G)
for G in time polynomial in |G|.
Lemma 3. Let G ∈ G be a graph and v ∈ V (G) and e ∈ E(G). Then it holds
that ω(G − v) and ω(G − e) are in {ω(G) − 1, ω(G)}.
Having these results, we can show the next theorem.
Theorem 19. The problem ω-Stability is in P for co-graphs.
Proof. Let G ∈ C be a co-graph. By Theorem 15 we can compute ω efficiently
for G and all induced subgraphs. In order to decide whether G is ω-stable, we
proceed as follows for every edge e = {u, v} ∈ E(G):
Case 1: G = G1 ∪ G2 for two co-graphs G1 , G2 , and either u, v ∈ V (G1 )
or u, v ∈ V (G2 ) holds, since there are no edges between G1 and G2 . Assume
without loss of generality that u, v ∈ V (G1 ). As ω(G) = max{ω(G1 ), ω(G2 )},
we efficiently check whether ω(G2 ) ≥ ω(G1 ) holds. In this case, we know that
e cannot be critical to G, because even if e would be ω-critical to G1 , using
Lemma 3, we still have ω(G − e) = max{ω(G1 − e), ω(G2 )} = max{ω(G1 ) −
1, ω(G2 )} = ω(G2 ). Otherwise, if ω(G1 ) > ω(G2 ) holds, we study whether e is
ω-critical for G1 by recursively selecting the appropriate case, this time with G1
as G. This is sufficient because if e is ω-critical for G1 , it is also ω-critical for G.
Case 2: G = G1 + G2 and u, v ∈ V (G1 ) or u, v ∈ V (G2 ). In this case, it is
sufficient to check whether e is ω-critical for the partial graph, i.e., G1 or G2 ,
containing u and v. That is because ω(G) = ω(G1 ) + ω(G2 ) holds and so, if e is
ω-critical for one of the two partial graphs, e is also critical for G. Once again,
we check this by recursively applying the appropriate case for the corresponding
partial graph.
Case 3: G = G1 + G2 and u, v are in different partial graphs. Assume that
u ∈ V (G1 ) and v ∈ V (G2 ) holds. Now, in order for e to be ω-critical, there must
exist only one clique V 0 ⊆ V (G1 ) with ω(G1 ) = |V 0 | as well as u ∈ V 0 and only
one clique V 00 ⊆ V (G2 ) with ω(G2 ) = |V 00 | and v ∈ V 00 . We can check both
conditions efficiently using Lemma 2. If this is the case, then all other cliques in
G1 are strictly smaller than V 0 and all other cliques in G2 are strictly smaller
than V 00 . Hence, the only clique of size ω(G) in G is V 0 ∪ V 00 , containing u and
v. Removing e = {u, v} from G causes ω(G) to be reduced by one since there
is only one clique of size ω(G) in G, and afterwards, it is missing the edge e in
G − e. Therefore, only in this case e is ω-critical.
The number of recursive calls is limited by dlog(|V (G)|)e, since every in-
ner node of G’s co-expression combines at least two nodes. Every case can be
Stability of Special Graph Classes 13
computed efficiently, such that we can determine for a co-graph G in time in
O(|E(G)| · log(|V (G)|) · |V (G)|c ) for some c ∈ N whether G is ω-stable. Conse-
quently, ω-Stability is in P for all co-graphs. q
As we now know that we can efficiently determine whether a given co-graph G
is ω-stable, we can exploit the fact that co-graphs are closed under complements
to obtain the following corollary.
Corollary 10. The problem α-Stability is in P for co-graphs.
The next corollary follows from Gallai’s theorem [7] and [6, Proposition 5].
Corollary 11. The problem β-Stability is in P for co-graphs.
At this point, we finish the study of stability problems for co-graphs, as all
open questions are answered, and turn to the problems related to unfrozenness.
The next two corollaries exploit the fact that co-graphs are closed under com-
plements and follow a similar argumentation.
Corollary 12. The problems β-Unfrozenness and α-Unfrozenness are in
P for co-graphs.
Corollary 13. The problem ω-Unfrozenness is in P for co-graphs.
Finally, we answer the last remaining open question related to unfrozenness
and co-graphs.
Theorem 20. The problem χ-Unfrozenness is in P for co-graphs.
Proof. Let G ∈ G be a co-graph and e = {u, v} ∈ E(G) a nonedge of G. Since
G has at least two vertices, u and v, either G = G1 + G2 or G = G1 ∪ G2 for
two co-graphs G1 , G2 holds. We handle both cases separately:
1. If G = G1 +G2 is true, then e must belong either to E(G1 ) or to E(G2 ), since
{{u, v} | u ∈ V (G1 ), v ∈ V (G2 )} ⊆ E(G), such that E(G) = E(G1 ) ∪ E(G2 ).
Without loss of generality assume that e ∈ E(G1 ) holds. If e is χ-unfrozen
for G1 , i.e., χ(G1 + e) = χ(G1 ), then e is χ-unfrozen for G, since χ(G + e) =
χ(G1 + e) + χ(G2 ) = χ(G1 ) + χ(G2 ) = χ(G) follows. Contrarily, if e is χ-
frozen for G1 , i.e., χ(G1 + e) = χ(G1 ) + 1, then e is χ-frozen for G as well,
as χ(G + e) = χ(G1 + e) + χ(G2 ) = χ(G1 ) + 1 + χ(G2 ) = χ(G) + 1 holds.
Hence, it is enough to determine whether e is χ-unfrozen or -frozen for G1
and we can follow the argumentation of this proof recursively for G1 .
2. If G = G1 ∪ G2 is true, e can belong to E(G1 ), E(G2 ), or E(G) \ (E(G1 ) ∪
E(G2 )). We split this into two sub-cases:
(a) If e ∈ E(G1 ) or e ∈ E(G2 ), we proceed as follows. Without loss of
generality assume e ∈ E(G1 ). Since χ(G) = max{χ(G1 ), χ(G2 )} holds,
an increase of χ(G1 ) affects χ(G) only if χ(G1 ) ≥ χ(G2 ). Otherwise, e is
χ-unfrozen for G (but not necessarily for G1 ). If χ(G1 ) ≥ χ(G2 ), then it
holds that if e is χ-unfrozen for G1 , it follows that e is χ-unfrozen for G,
14 R. Weishaupt and J. Rothe
since χ(G + e) = max{χ(G1 + e), χ(G2 )} = χ(G1 + e) = χ(G1 ) = χ(G)
is true. Similarly, if e is χ-frozen for G1 , it follows that e is χ-frozen for
G, since χ(G + e) = max{χ(G1 + e), χ(G2 )} = χ(G1 + e) = χ(G1 ) + 1 =
χ(G)+1. Consequently, it is enough to determine whether e is χ-unfrozen
or -frozen for G1 and we can follow the argumentation of this proof
recursively for G1 .
(b) If e ∈ E(G) \ (E(G1 ) ∪ E(G2 )), then u ∈ V (G1 ) and v ∈ V (G2 ) follows.
Now, if χ(G1 ) = χ(G2 ) = 1 is true, it follows that e is χ-frozen for G,
since χ(G+e) = 1+1 = 2 > 1 = max{χ(G1 ), χ(G2 )} = χ(G). Contrarily,
if χ(G1 ) > 1 or χ(G2 ) > 1, it follows that e is χ-unfrozen for G since G1
and G2 share no edge but e. Because of that we can arrange the colors
for V (G1 ) and V (G2 ) in such a way that both vertices incident to e have
different colors, resulting in χ(G + e) = χ(G).
Following these cases, we can efficiently determine for every nonedge e ∈ E(G)
whether it is χ-frozen or -unfrozen for G, resulting in χ-Unfrozenness ∈ P for
all co-graphs. q
5 Conclusion
We have provided 48 tractability results regarding the stability, vertex-stability,
and unfrozenness problems when restricted to special graph classes. In particu-
lar, we studied these three problems for four important graph classes and four
central graph parameters. Doing so, our work provides some baseline for further,
more expanding work along this line of research. For future work, we propose
to study further special graph classes that are not covered here. Besides the
study of stability for other graph classes, one can also study the concept of cost
of stability:3 Given a graph, the question is how costly it is to stabilize it. In
other words, what is the smallest number of vertices or edges to be added to or
removed from the graph such that the resulting graph is stable or unfrozen with
respect to some graph parameter. Relatedly, it would make sense to combine
these two approaches and study the cost of stability for special graph classes.
Acknowledgments
We thank the anonymous reviewers for helpful comments. This work was sup-
ported in part by Deutsche Forschungsgemeinschaft under grant RO 1202/21-1.
References
1. Bachrach, Y., Elkind, E., Malizia, E., Meir, R., Pasechnik, D., Rosenschein, J.,
Rothe, J., Zuckerman, M.: Bounds on the cost of stabilizing a cooperative game.
Journal of Artificial Intelligence Research 63, 987–1023 (2018)
3
Bachrach et al. [1] study a related notion of “cost of stability” for cooperative games.
Stability of Special Graph Classes 15
2. Berge, C.: Perfect graphs. In: Six Papers on Graph Theory. pp. 1–21. Indian Sta-
tistical Institute (1963)
3. Bollobás, B.: Modern Graph Theory. Springer-Verlag (1998)
4. Corneil, D., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discret.
Appl. Math. 3(3), 163–174 (1981)
5. Corneil, D., Perl, Y., Stewart, L.: A linear recognition algorithm for cographs.
SIAM Journal on Computing 14(4), 926–934 (1985)
6. Frei, F., Hemaspaandra, E., Rothe, J.: Complexity of stability. Journal of Computer
and System Sciences (to appear), conference version appeared in the proceedings
of the 31st International Symposium on Algorithms and Computation (ISAAC’20),
Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, 19:1–19:14,
2020
7. Gallai, T.: Über extreme Punkt- und Kantenmengen. Ann. Univ. Sci. Budapest,
Eotvos Sect. Math 2, 133–138 (1953)
8. Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Exact analysis of Dodgson elec-
tions: Lewis Carroll’s 1876 voting system is complete for parallel access to NP.
Journal of the ACM 44(6), 806–825 (1997)
9. Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Raising NP lower bounds to
parallel NP lower bounds. SIGACT News 28(2), 2–13 (1997)
10. Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections.
Theoretical Computer Science 349(3), 382–391 (2005)
11. Hopcroft, J., Karp, R.: An n5/2 algorithm for maximum matching in bipartite
graphs. SIAM Journal on Computing 2, 225–231 (1973)
12. Jackson, M.: Social and Economic Networks. Princeton University Press (2008)
13. Khor, S.: Application of graph coloring to biological networks. IET Systems Biology
4(3), 185–192 (2010)
14. Kőnig, D.: Gráfok és mátrixok. Matematikai és Fizikai Lapok 38, 116–119 (1931)
15. Minor, E., Urban, D.: A graph-theory framework for evaluating landscape connec-
tivity and conservation planning. Conservation biology 22(2), 297–307 (2008)
16. Papadimitriou, C.: Computational Complexity. Addison-Wesley, second edn.
(1995)
17. Papadimitriou, C., Yannakakis, M.: The complexity of facets (and some facets of
complexity). Journal of Computer and System Sciences 28(2), 244–259 (1984)
18. Papadimitriou, C., Zachos, S.: Two remarks on the power of counting. In: Pro-
ceedings of the 6th GI Conference on Theoretical Computer Science. pp. 269–276.
Springer-Verlag Lecture Notes in Computer Science #145 (1983)
19. Rothe, J.: Complexity Theory and Cryptology. An Introduction to Cryptocom-
plexity. EATCS Texts in Theoretical Computer Science, Springer-Verlag (2005)
20. Rothe, J., Spakowski, H., Vogel, J.: Exact complexity of the winner problem for
Young elections. Theory of Computing Systems 36(4), 375–386 (2003)
21. Wagner, K.: More complicated questions about maxima and minima, and some
closures of NP. Theoretical Computer Science 51(1–2), 53–80 (1987)
22. Wagner, K.: Bounded query classes. SIAM Journal on Computing 19(5), 833–846
(1990)
23. Weishaupt, R., Rothe, J.: Stability of special graph classes. Tech. Rep.
arXiv:2106.01496 [cs.CC], arXiv.org (Jun 2021)