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 variants 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 cographs.
Frei et al. [
Furthermore, Frei et al. [
Commons License Attribution 4.0 International (CC BY 4.0).
for k = 3 and DP-complete for k 4, respectively, where DP was introduced by
Papadimitriou and Yannakakis [
Overall, the results of Frei et al. [
This obstacle motivates us to study whether there are scenarios that allow for
e cient 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. [
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
We follow the notation of Frei et al. [
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 2 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 VE CCoorr.. 33 TThhmm.. 77 Unfrozenness Prop. 1 Thm. 8
B Cor. 4 Cor. 4 Cor. 6 Cor. 4 Cor. 4 Thm. 12 Cor. 4 Cor. 4 Cor. 5 Cor. 4 Cor. 4 Thm. 11
C Cor. 10 Thm. 17 Cor. 12 Cor. 11 Cor. 8 Cor. 12 Thm. 19 Cor. 9 Cor. 13 Thm. 18 Thm. 16 Thm. 20 if (G) is changed by deleting e), e is said to be -critical. Stability and criticality are de ned analogously for a vertex v 2 V (G) instead of an edge e 2 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 de ned 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 vertexunfrozenness : 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 vertexcriticality 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 , de ne -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. [
holds that all (induced) subgraphs H of G satisfy H 2 J .
The notation of perfect graphs was originally introduced by Berge [
(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 complexity classes NP, DP, and 2P mentioned in the introduction; note that P NP
Rothe [
For the sake of self-containment, we here state Gallai's theorem [
jV (G)j = (G) + (G): 3
In this section, we provide general results that hold for speci c 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 2 P for all G 2 J .
compute (G v) e ciently and compare it to (G). If there is no vertex such that the values di er, G is -vertex-stable. This approach is computable in time polynomial in jGj, so that -VertexStability 2 P for all G 2 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 2 P for all G 2 J .
The rst 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 [
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 2 G be a perfect graph. Then it holds that G is !-vertexstable 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.
While the above results are related to the concepts of stability and vertexstability, the subsequent two results address the topic of unfrozenness. Theorem 5. Let J G be a graph class closed under complements and subgraphs. If or is tractable for J , then !-Unfrozenness 2 P for all G 2 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 subgraphs. If ! is tractable for J , then - and -Unfrozenness 2 P for all G 2 J . 4
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 [
With these two observations we can now inspect several graph classes. In the
following subsections we study the problems -Stability, -VertexStability,
and -Unfrozenness with 2 f ; ; !; g, restricted to special graph classes.
Frei et al. [
We start with investigating trees and forests. 4.1
Trees and Forests
of length greater than or equal to 3. Furthermore, G is a forest (i.e., G 2 F ) if
there exist trees G1; : : : ; Gn 2 T such that G = G1 [ [ Gn. For every tree
G 2 T , it holds that jE(G)j = jV (G)j 1 (see, e.g., Bollobas [
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 [
Now, let G 2 F with G = G1 [ [ Gn and Gi 2 T , 1 i n, be a forest. It is easy to check that (G) = Pin=1 (Gi), (G) = Pin=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 2 f ; ; !; g be a graph parameter. Then the problems Stability and -VertexStability are in P for all forests.
and -VertexStability belong to P.
2 f ; ; !; g, the problems -Stability
We now focus on the unfrozenness problems. All trees and forests with fewer
than three vertices are trivial to handle (see the technical report [
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 2 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 ffu; vg j u 2
simple observations.
Observation 3. Let G 2 B be a bipartite graph. Then E(G) = ;, and (G) = !(G) = 2 if E(G) 6= ;. (G) = !(G) = 1 if
Consequently, we can e ciently calculate and ! for all bipartite graphs.
The proof of the next observation (see [
Observation 4. We can calculate (G) and (G) e ciently for G 2 B.
Furthermore, as the class of bipartite graphs is closed under subgraphs and induced subgraphs, the following corollary follows from Theorem 2. Corollary 4. For every 2 f ; ; !; g, 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 [
We now provide results for bipartite graphs with more than one edge. Proposition 3. Every bipartite graph G with jE(G)j 2 is -stable.
Proof. that (G
e) = 2 = (G) and, thus, G is -stable. e) 6= ;, it holds q
Furthermore, we can characterize -vertex-stability.
Theorem 9. Let G be a bipartite graph with jE(G)j 2. G is -vertex-stable if and only if for all v 2 V (G) it holds that deg(v) < jE(G)j.
Proof. Assume G to be -vertex-stable. Furthermore, as we assume that jE(G)j 2, it holds that (G) = 2. Then there cannot exist a vertex v 2 V (G) with deg(v) = jE(G)j, 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 2 V (G) we have deg(v) < jE(G)j. Hence, no matter what vertex v 2 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 jE(G)j 2 is !-stable.
such that G is !-stable. e) = 2 = !(G) as E(G e) 6= ; holds, q
Lastly, we can also characterize !-vertex-stability.
Theorem 10. Let G be a bipartite graph with jE(G)j 2. G is !-vertex-stable if and only if for all v 2 V (G) it holds that deg(v) < jE(G)j.
holds that !(G v) = 2 = !(G). If there is one v 2 V (G) with deg(v) = jE(G)j, we have !(G v) = 1 as E(G v) = ;, a contradiction to G's !-vertex-stability.
all v 2 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. Theorem 11. Let G be a bipartite graph. G is possesses no P3 as an induced subgraph. -unfrozen if and only if G Proof. We prove both directions separately. First, assume G is -unfrozen but contains P3 as an induced subgraph. Write V (P3) = fv1; v2; v3g and E(P3) = ffv1; v2g; fv2; v3gg for the corresponding vertices and edges. Then e = fv1; v3g 2 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 = fu; vg 2 E(G) such that (G + e) = 3 > 2 = (G). Denote the two disjoint vertex sets of G by V1 [ V2 = V (G). Obviously, u 2 V1 and v 2 V2 cannot be true, since then (G + e) = 2 would hold. Therefore, without loss of generality, we assume u; v 2 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 2 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 2 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 [
Lemma 1. Let G be a bipartite graph and u 2 V (G). If (G u) = (G) then there exists some vertex cover V 0 V (G) with u 2 V 0 and jV 0j = (G). 1, Theorem 12. For every G 2 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 [
F
Corollary 7. The problems - and -Unfrozenness as well as the problem
-Frozenness belong to P for all trees and forests.
First of all, we recursively de ne co-graphs, following a slightly adjusted de
nition by Corneil et al. [
De nition 1 (co-graph). The graph G = (fvg; ;) is a co-graph. If G1 and G2 are co-graphs, then G1 [ G2 and G1 + G2 are co-graphs, too.
common (see, e.g., [
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 = (fv1; v2; v3; v4g; ffv1; v2g; fv2; v3g; fv3; v4g; fv4; v1gg).
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. [
Combining the previous results with the next one by Corneil et al. [
Theorem 15. Let G 2 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]) = maxf (G[v1]); (G[v2])g, 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).
A result similar to the previous one for
was given by Corneil et al. [
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]) = maxf (G[v1]); (G[v2])g 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 e ciently calculate on these results, we can state the following theorems. for co-graphs. Based Theorem 16. For every G 2 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 2 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 [
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. [
Corollary 9. For all G 2 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 2 C with jV (G)j > 1 and let u 2 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 2 V (G1), u is -critical for G1. Proposition 6. Let G 2 C and e = fu; vg 2 E(G). If u and v are -critical for G, then e is -critical for G as well.
Proof. Let G 2 C be a co-graph and e = fu; vg 2 E(G) an edge with two -critical vertices u; v 2 V (G). First, we study the case that G = G1 + G2 as well as u 2 V (G1) and v 2 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 [
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 2 V (G1) and v 2 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) = maxf (G1); (G2)g 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 2 C be a co-graph. We can compute (G) e ciently and,
according to Observation 1 in [
(G v); (G u)
| 2f (G){z1; (G)g }
(G
e)
(G):
Hence, if (G v) = (G) or (G u) = (G), which we can compute e ciently,
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 [
Next, we want to study the problem of !-Stability for co-graphs. To do so, we need the following lemmas.
Lemma 2. Let G 2 C be a co-graph. We can compute all cliques of size !(G) for G in time polynomial in jGj.
Lemma 3. Let G 2 G be a graph and v 2 V (G) and e 2 E(G). Then it holds that !(G v) and !(G e) are in f!(G) 1; !(G)g.
Having these results, we can show the next theorem.
Theorem 19. The problem !-Stability is in P for co-graphs.
for G and all induced subgraphs. In order to decide whether G is !-stable, we proceed as follows for every edge e = fu; vg 2 E(G):
Case 1: G = G1 [ G2 for two co-graphs G1; G2, and either u; v 2 V (G1) or u; v 2 V (G2) holds, since there are no edges between G1 and G2. Assume without loss of generality that u; v 2 V (G1). As !(G) = maxf!(G1); !(G2)g, we e ciently 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) = maxf!(G1 e); !(G2)g = maxf!(G1) 1; !(G2)g = !(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 su cient because if e is !-critical for G1, it is also !-critical for G.
Case 2: G = G1 + G2 and u; v 2 V (G1) or u; v 2 V (G2). In this case, it is su cient 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 di erent partial graphs. Assume that u 2 V (G1) and v 2 V (G2) holds. Now, in order for e to be !-critical, there must exist only one clique V 0 V (G1) with !(G1) = jV 0j as well as u 2 V 0 and only one clique V 00 V (G2) with !(G2) = jV 00j and v 2 V 00. We can check both conditions e ciently 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 = fu; vg 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.
ner node of G's co-expression combines at least two nodes. Every case can be computed e ciently, such that we can determine for a co-graph G in time in O(jE(G)j log(jV (G)j) jV (G)jc) for some c 2 N whether G is !-stable. Consequently, !-Stability is in P for all co-graphs. q
As we now know that we can e ciently 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 [
-Stability is in P for co-graphs.
At this point, we nish 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 complements 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 2 G be a co-graph and e = fu; vg 2 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 ffu; vg j u 2 V (G1); v 2 V (G2)g E(G), such that E(G) = E(G1) [ E(G2).
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) n (E(G1) [ E(G2)). We split this into two sub-cases: (a) If e 2 E(G1) or e 2 E(G2), we proceed as follows. Without loss of generality assume e 2 E(G1). Since (G) = maxf (G1); (G2)g holds, an increase of (G1) a ects (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, since (G + e) = maxf (G1 + e); (G2)g = (G1 + e) = (G1) = (G) is true. Similarly, if e is -frozen for G1, it follows that e is -frozen for G, since (G + e) = maxf (G1 + e); (G2)g = (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 2 E(G) n (E(G1) [ E(G2)), then u 2 V (G1) and v 2 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 = maxf (G1); (G2)g = (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 di erent colors, resulting in (G + e) = (G).
whether it is -frozen or -unfrozen for G, resulting in -Unfrozenness 2 P for all co-graphs. q 5
We have provided 48 tractability results regarding the stability, vertex-stability, and unfrozenness problems when restricted to special graph classes. In particular, 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.
We thank the anonymous reviewers for helpful comments. This work was
supported in part by Deutsche Forschungsgemeinschaft under grant RO 1202/21-1.
3 Bachrach et al. [