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)