Öznur Yaşar Diner

Daniël Paulusma
email: daniel.paulusma@durham.ac.uk

Christophe Picouleau
email: christophe.picouleau@cnam.fr

Bernard Ries
email: bernard.ries@dauphine.fr

Contraction Blockers for Graphs with Forbidden Induced Paths

We consider the following problem: can a certain graph parameter of some given graph be reduced by at least d for some integer d via at most k edge contractions for some given integer k? We examine three graph parameters: the chromatic number, clique number and independence number. For each of these graph parameters we show that, when d is part of the input, this problem is polynomial-time solvable on P4-free graphs and NP-complete as well as W[1]-hard, with parameter d, for split graphs. As split graphs form a subclass of P5-free graphs, both results together give a complete complexity classification for Pfree graphs. The W[1]-hardness result implies that it is unlikely that the problem is fixed-parameter tractable for split graphs with parameter d. But we do show, on the positive side, that the problem is polynomialtime solvable, for each parameter, on split graphs if d is fixed, i.e., not part of the input. We also initiate a study into other subclasses of perfect graphs, namely cobipartite graphs and interval graphs.

Introduction

A graph modification problem is usually defined as follows. We fix a graph class G and a set S of one or more graph operations. The input consists of a graph G and an integer k. The question is whether G can be modified into a graph H ∈ G by using at most k operations from S. Now, instead of fixing a particular graph class G, one may want to fix a graph parameter π instead. Then the question becomes whether G can be modified, by using at most k operations from S, into a graph H with π(H) ≤ π(G) -d for some threshold d, which is a nonnegative integer that can either be fixed or be part of the input. These problems have been studied in a number of papers [2-4, 11, 21-23], where the graph parameters that were considered are the chromatic number, clique number, independence number, matching number, and the vertex cover number, while the set S was a singleton consisting of a vertex deletion, edge deletion or edge addition. In this paper we focus on another graph operation: the edge contraction, for which the graph modification problem has been studied for fixed graph classes already in the early eighties [START_REF] Watanabe | On the removal of forbidden graphs by edge-deletion or by edge-contraction[END_REF][START_REF] Watanabe | On the NP-hardness of edgedeletion and -contraction problems[END_REF] but not yet for fixed graph parameters.

Let G be a finite undirected graph with no self-loops and no multiple edges. The contraction of an edge uv of G removes the vertices u and v from G, and replaces them by a new vertex made adjacent to precisely those vertices that were adjacent to u or v in G. We say that a graph G can be k-contracted into a graph H if G can be modified into H by a sequence of at most k edge contractions.

We consider the following generic problem, where we fix the graph parameter π and the threshold d (that is, they are not part of the input): d-Contraction Blocker(π) Instance: a graph G = (V, E) and a nonnegative integer k. Question: can G be k-contracted into a graph H with π(H) ≤ π(G) -d?

We also consider the following version of the above problem where d is part of the input (thus only π is fixed):

Contraction Blocker(π) Instance: a graph G = (V, E) and two nonnegative integers d, k. Question: can G be k-contracted into a graph H with π(H) ≤ π(G) -d?

These problems have been studied implicitly in the literature already in various settings. For instance, Belmonte et al. [START_REF] Belmonte | Parameterized complexity of three edge contraction problems with degree constraints[END_REF] proved that 1-Contraction Blocker(∆), where ∆ denotes the maximum vertex-degree, is NP-complete even for split graphs. In this paper we consider the following graph parameters: the chromatic number χ, the clique number ω and the independence number α of a graph. The following two results follow directly from known results.

First, 1-Contraction Blocker(χ) is NP-complete even for graphs of chromatic number 3. This can be seen as follows. Consider the problem Bipartite Contraction, which is that of testing whether a graph can be made bipartite by at most k edge contractions. It is readily seen that 1-Contraction Blocker(χ) and Bipartite Contraction are equivalent for graphs of chromatic number 3. Heggernes, van t Hof, Lokshtanov and Paul [START_REF] Heggernes | Obtaining a Bipartite Graph by Contracting Few Edges[END_REF] observed that Bipartite Contraction is NP-complete by reducing from the NP-complete problem Edge Bipartization, which is that of testing whether a graph can be made bipartite by deleting at most k edges. Given an instance (G, k) of Edge Bipartization, they obtain an instance (G , k ) of Bipartite Contraction by replacing every edge in G by a path of sufficiently large odd length. Note that the resulting graph G has chromatic number 3.

Second, 1-Contraction Blocker(α) is NP-complete even for graphs with independence number 2. This can be seen as follows. Golovach, Heggernes, van 't Hof and Paul [START_REF] Golovach | Hadwiger Number of Graphs with Small Chordality[END_REF] considered the s-Club Contraction problem, which takes as input a graph G and an integer k and asks whether G can be k-contracted into a graph with diameter at most s for some fixed integer s. They showed that 1-Club Contraction is NP-complete even for cobipartite graphs. Graphs of diameter 1 are complete graphs, that is, graphs with independence number 1, whereas cobipartite graphs have independence number at most 2.

Our Results. In Section 2 we first introduce some definitions and notations. In the same section we show that 1-Contraction Blocker(ω) is NP-complete even for graphs with clique number 3. In Section 3 we prove that Contraction Blocker(π) is polynomial-time solvable on cographs for π ∈ {α, χ, ω). Cographs are also known as P 4 -free graphs (a graph is P -free if it has no induced path on vertices).

Our result generalizes a recent result of Golovach et al. [START_REF] Golovach | Hadwiger Number of Graphs with Small Chordality[END_REF] who proved that the Hadwiger Number problem is polynomial time solvable on cographs. This problem is to test whether a graph contains the complete graph K r as a minor (or equivalently as a contraction) for some given integer r, which is equivalent to the Contraction Blocker(α) problem restricted to instances (G, d, k) where d = α(G) -1 and k = |V (G)| -r. Our result can be viewed as best possible as in Section 4 we show that for π ∈ {α, χ, ω) the Contraction Blocker(π) problem is NP-complete for split graphs, which form a subclass of P 5 -free graphs. We show that the same hardness reduction can also be used to prove that the three problems, restricted to split graphs, are W[1]-hard when parameterized by d. The latter result means that for split graphs these problems are unlikely to be fixed-parameter tractable with parameter d. We complement the hardness results for split graphs by proving in the same section that, for all (fixed) d ≥ 1, the d-Contraction Blocker(π) problem is polynomial-time solvable for split graphs if π ∈ {α, χ, ω). See Table 1 for an overview of these results.

Cographs and split graphs are subclasses of perfect graphs. Section 5 contains, besides a number of directions for future work, some initial results for other subclasses of perfect graphs, namely for interval graphs and cobipartite graphs.

Preliminaries

We denote a graph by G = (V (G), E(G)), where V (G) is the vertex set and E(G) is the edge set. We may write G = (V, E) if no confusion is possible. All graphs considered are finite, undirected and without self-loops or multiple edges. Let G = (V, E) be a graph. The complement of G is the graph G = (V, E) with vertex set V and an edge between two vertices u and v if and only if uv / ∈ E. For a subset S ⊆ V , we let G[S] denote the induced subgraph of G, which has vertex set S and edge set {uv ∈ E | u, v ∈ S}. A set I ⊆ V is an independent set of G if no two vertices in I are adjacent to each other. The independence number α(G) is the number of vertices in a maximum independent set of G. A subset C ⊆ V is called a clique of G if any two vertices in C are adjacent to each other. The clique number ω(G) is the number of vertices in a maximum clique of G. For a positive integer k, a k-coloring of G is a mapping c : V → {1, 2, . . . , k} such that c(u) = c(v) whenever uv ∈ E. The chromatic number χ(G) is the smallest number k for which G has a k-coloring. Recall that the contraction of an edge uv ∈ E removes the vertices u and v from G, and replaces them by a new vertex made adjacent to precisely those vertices that were adjacent to u or v in G (so neither self-loops nor multiple edges are created). We may also say that a vertex u is contracted onto v, and we use v to denote the new vertex resulting from the edge contraction.

Let G be a graph and let {H 1 , . . . , H p } be a set of graphs. We say that G is (H 1 , . . . , H p )-free if G has no induced subgraph isomorphic to a graph in {H 1 , . . . , H p }. If p = 1 we may write H 1 -free instead of (H 1 )-free. For n ≥ 1, the graph P n denotes the path on n vertices, that is,

V (P n ) = {u 1 , . . . , u n } and E(P n ) = {u i u i+1 | 1 ≤ i ≤ n -1}. For n ≥ 3, the graph C n denotes the cycle on n vertices, that is, V (C n ) = {u 1 , . . . , u n } and E(C n ) = {u i u i+1 | 1 ≤ i ≤ n -1} ∪ {u n u 1 }.
A graph G = (V, E) is a split graph if G has a split partition, which is a partition of its vertex set into a clique K and an independent set I. A split partition (K, I) of a graph G is called maximal if K ∪ {u} is not a clique for all u ∈ I. A split partition (K, I) of a graph G is called minimal if I ∪ {v} is not an independent set for all v ∈ K. Split graphs coincide with (2P 2 , C 4 , C 5 )-free graphs [START_REF] Földes | Split graphs, 8th South-Eastern[END_REF] (where 2P 2 is the disjoint union of two copies of P 2 ). A split graph is chordal, that is, contains no induced cycle on four or more vertices. A graph is cobipartite if it is the complement of a bipartite graph, which is a graph whose vertex set can be split into two non-empty subsets A and B such that any edge is between a vertex of A and a vertex of B. A graph is an interval graph if it is the intersection graph of a set of closed intervals on the real line, i.e., its vertices correspond to the intervals and two vertices are adjacent in G if and only if their intervals have at least one point in common. A P 4 -free graph is also called a cograph. A graph is perfect if the chromatic number of every induced subgraph equals the size of a largest clique in that subgraph. Chordal graphs, cobipartite graphs, cographs, interval graphs and split graphs all form subclasses of perfect graphs.

We finish this section by showing the following general result which motivated our study of special graph classes. Note that it is trivial to solve 1-Contraction Blocker(χ) in polynomial-time on graphs with chromatic number 2 as well as 1-Contraction Blocker(ω) on graphs with clique number 2. 1Theorem 1 (♠). 1-Contraction Blocker(π) is NP-complete for (i) graphs with independence number 2 if π = α; (ii) graphs with chromatic number 3 if π = χ; (iii) graphs with clique number 3 if π = ω.

Cographs

Before presenting our results on cographs we first give some additional terminology. Let G 1 and G 2 be two vertex-disjoint graphs. The join operation ⊗ adds an edge between every vertex of G 1 and every vertex of G 2 . The union operation ⊕ creates the disjoint union of G 1 and G 2 which is the graph with vertex set

V (G 1 ) ∪ V (G 2 ) and edge set E(G 1 ) ∪ E(G 2 ). We denote the disjoint union of G 1 and G 2 by G 1 ⊕ G 2 .
We denote the disjoint union of r copies of a graph G by rG.

It is well known (see, for example, [START_REF] Brandstädt | Graph Classes: A Survey[END_REF]) that a graph G is a cograph if and only if G can be generated from K 1 by a sequence of operations, where each operation is either a join or a union. Such a sequence corresponds to a decomposition tree T , which has the following properties:

1. its root r corresponds to the graph G r = G; 2. every leaf x of T corresponds to exactly one vertex of G, and vice versa, implying that x corresponds to a unique single-vertex graph G x ; 3. every internal node x of T has at least two children, is either labeled ⊕ or ⊗, and corresponds to an induced subgraph G x of G defined as follows:

• if x is a ⊕-node, then G x is the disjoint union of all graphs G y where y is a child of x; • if x is a ⊗-node, then G x is the join of all graphs G y where y is a child of x.

A cograph G may have more than one such tree but has exactly one unique tree [START_REF] Corneil | Complement reducible graphs[END_REF], called the cotree T G of G, if the following additional property is required:

4. Labels of internal nodes on the (unique) path from any leaf to r alternate between ⊕ and ⊗.

Note that T G has O(n) vertices. For our purposes we must modify T G by applying the following known procedure (see e.g. [START_REF] Bodlaender | The pathwidth and treewidth of cographs[END_REF]). Whenever an internal node x of T G has more than two children y 1 and y 2 , we remove the edges xy 1 and xy 2 and add a new vertex x with edges xx , x y 1 and x y 2 . If x is a ⊕-node, then x is a ⊕-node, and if x is a ⊗-node, then x is a ⊗-node. Applying this rule exhaustively yields a tree in which each internal node has exactly two children. We denote this tree by

T G . Because T G has O(n) vertices, modifying T G into T G takes linear time.
Corneil, Perl and Stewart [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF] proved that the problem of deciding whether a graph with n vertices and m edges is a cograph can be solved in time O(n + m). They also showed that in the same time it is possible to construct its cotree (if it exists). As modifying T G into T G takes O(n + m) time, we obtain the following lemma.

Lemma 1. Let G be a graph with n vertices and m edges. Deciding if G is a cograph and constructing T G (if it exists) can be done in time O(n + m).

For two integers k and l we say that a graph G can be (k, l)-contracted into a graph H if G can be modified into H by a sequence containing k edge contractions and l vertex deletions. Note that cographs are closed under edge contraction and under vertex deletion. In fact, to prove our results for cographs, we will prove that the problem whether a cograph G can be (k, l)-contracted into a cograph H with π(H) ≤ π(G) -d is polynomial-time solvable for all given integers d, k, l and for all π ∈ {α, χ, ω}.

Theorem 2. For π ∈ {α, χ, ω}, the Contraction Blocker(π) problem can be solved in O(n 2 + mn + k 3 n) time on cographs with n vertices and m edges.

Proof. First consider π = α. Let G be a cograph with n vertices and m edges that together with an integer k forms an instance of Contraction Blocker(α). We first construct T G . We then consider each node of T G by following a bottom-up approach starting at the leaves of T G and ending in its root r.

Let x be a node of T G . Recall that G x is the subgraph of G induced by all vertices that corresponds to leaves in the subtree of T G rooted at x. We associate a table with x that records the following data: for each pair of integers i, j ≥ 0 with i + j ≤ k we compute the largest integer d such that G x can be (i, j)contracted into a graph H x with α(H x ) ≤ α(G x ) -d. We denote this integer d by d(i, j, x). Let i, j ≥ 0 with i + j ≤ k.

Case 1. x is a leaf. Then G x is a 1-vertex graph meaning that d(i, j, x) = 0 if j = 0, whereas d(i, j, x) = 1 if j ≥ 1.

Case 2. x is a ⊕-node. Let y and z be the two children of x. Then, as G x is the disjoint union of G y and G z , we find that α(G x ) = α(G y ) + α(G z ). Hence, we have

d(i, j, x) = max {α(G x ) -(α(G y ) -d(a, b, y) + α(G z ) -d(i -a, j -b, z)) | 0 ≤ a ≤ i, 0 ≤ b ≤ j} = max {d(a, b, y) + d(i -a, j -b, z) | 0 ≤ a ≤ i, 0 ≤ b ≤ j}. Case 3. x is a ⊗-node. Since x is a ⊗-node, G
x is connected and as such has a spanning tree T . If i + j ≥ |V (G x )| and j ≥ 1, then we can contract i edges of T in the graph G x followed by j vertex deletions. As each operation will reduce G x by exactly one vertex, this results in the empty graph. Hence, d(i, j, x) = α(G x ). From now on assume that i + j < |V (G x )| or j = 0. As such, any graph we can obtain from G x by using i edge contractions and j vertex deletions is non-empty and hence has independence number at least 1.

Let y and z be the two children of x. Then, as G x is the join of G y and G z , we find that α(G x ) = max{α(G y ), α(G z )}. In order to determine d(i, j, x) we must do some further analysis. Let S be a sequence that consists of i edge contractions and j vertex deletions of G x such that applying S on G x results in a graph H x with α(H x ) = α(G x ) -d(i, j, x). We partition S into five sets S e y , S e z , S e yz , S v y , S v z , respectively, as follows. Let S e y and S e z be the set of contractions of edges with both end-vertices in G y and with both end-vertices in G z , respectively. Let First assume that S e yz = ∅. Then a y + a z = i. Let H y be the graph obtained from G y after applying the subsequence of S, consisting of operations in S e y ∪ S v y , on G y . Let H z be defined analogously. Then we have

α(H x ) = max{α(H y ), α(H z )} = max{α(G y ) -d(a y , b, y), α(G z ) -d(a z , j -b, z)} = max{α(G y ) -d(a y , b, y), α(G z ) -d(i -a y , j -b, z)},
where the second equality follows from the definition of S. Now assume that S e yz = ∅. Recall that i+j < |V (G x )| or j = 0. Hence α(H x ) ≥ 1. Our approach is based on the following observations. First, contracting an edge with one end-vertex in G y and the other one in G z is equivalent to removing these two end-vertices and introducing a new vertex that is adjacent to all other vertices of G x (such a vertex is said to be universal).

Second, assume that G y contains two distinct vertices u and u and that G z contains two distinct vertices v and v . Suppose that we are to contract two edges from {uv, uv , u v, u v }. Contracting two edges of this set that have a common end-vertex, say edges uv and uv , is equivalent to deleting u, v, v from G x and introducing a new universal vertex. Contracting two edges with no common end-vertex, say uv and u v , is equivalent to deleting all four vertices u, u , v, v from G x and introducing two new universal vertices. Because the two new universal vertices in the latter choice are adjacent, whereas the vertex u may not be universal after making the former choice, the latter choice decreases the independence number by the same or a larger value than the former choice. Hence, we may assume without loss of generality that the latter choice happened. More generally, the contracted edges with one end-vertex in G y and the other one in G z can be assumed to form a matching. We also note that introducing a new universal vertex to a graph does not introduce any new independent set other than the singleton set containing the vertex itself.

We conclude that each edge contraction in S e yz may be considered to be equivalent to deleting one vertex from G y and one from G z and introducing a new universal vertex. If one of the two graphs G y or G z becomes empty in this way, then an edge contraction in S e yz can be considered to be equivalent to the deletion of a vertex of the other one. Finally, if both sets G y and G z become empty, then we can stop as in that case H x has independence number 1 (which we assumed was the smallest value of α(H x )).

By the above observations and the definition of S we find that α(H x ) = max{1, α(G y )-d(a y , b+i-a y -a z , y), α(G z )-d(a z , j-b+i-a y -a z , z)}.

Hence we can do as follows. We consider all tuples (a y , b) with 0 ≤ a y ≤ i and 0 ≤ b ≤ j and compute max{α(G y ) -d(a y , b, y), α(G z ) -d(i -a y , j -b, z)}. Let α x be the minimum value over all values found. We then consider all tuples (a y , a z , b) with a y ≥ 0, a z ≥ 0, a y + a z ≤ i and 0 ≤ b ≤ j and compute max{1, α(G y )-d(a y , b+i-a y -a z , y), α(G z )-d(a z , j-b+i-a y -a z , z)}. Let α x be the minimum value over all values found. Then d(i, j, x) = α(G x )-min{α x , α x }.

After reaching the root r, we let our algorithm return the integer d(k, 0, r). By construction, d(k, 0, r) is the largest integer such that G = G r can be kcontracted into a graph H with α(H) ≤ α(G) -d(k, 0, r). We are left to analyze the running time.

Constructing T G can be done in O(n + m) time by Lemma 1. We now determine the time it takes to compute one entry d(i, j, x) in the table associated with a node x. It takes linear time to compute the independence number of a cograph2 . The total number of tuples (a y , b) and (a y , a z , b) that we need to consider is O(k 3 ). Note that the table associated with a node x has O(k 2 ) entries but that we only have to compute α(G x ) once. Hence, it takes O(n

+ m + k 3 ) time to construct a table for a node. As T G has O(n) vertices, the total running time is O(n + m) + O(n(n + m + k 3 )) = O(n 2 + mn + k 3 n).
Now consider π = χ. Note that we cannot consider the complement of a cograph (which is a cograph) because an edge contraction in a graph does not correspond to an edge contraction in its complement. However, we can re-use the previous proof after making a few modifications. Let G be a cograph with n vertices and m edges that together with an integer k forms an instance of Contraction Blocker(χ). We follow the same approach as in the proof for n = α. We only have to swap Cases 2 and 3 after observing that χ(G x ) = max{χ(G y ), χ(G z )} if x is a ⊕-node with y and z as its two children and χ(G x ) = χ(G y ) + χ(G z ) if x is a ⊗-node. We can use the same arguments as used in the proof for n = α for the running time analysis as well; we only have to observe that it takes O(n + m) time to compute the chromatic number of a cograph (using the same arguments as before or another algorithm of [START_REF] Chvátal | Four classes of perfectly orderable graphs[END_REF]).

Finally consider π = ω. As cographs are perfect and closed under edge contractions, the proof follows immediately from the corresponding result for π = χ.

Remark. As can be seen from the proofs of our results, our algorithms for solving Contraction Blocker(π) on cographs for π ∈ {α, χ, ω} in fact determine the largest integer d for which the input graph G can be k-contracted into a graph H with π(H) ≤ π(G) -d.

We first show the following result.

-contracted G into a graph G with α(G ) = |I | + 1 ≤ |I | + |I | -(|I | -1) ≤ |I | + |I | -d = α(G) -d. So, (G, k) is a yes-instance in this case. If k ≤ |I | -1, we contract each vertex of an arbitrary subset of k vertices of I onto a neighbor in K. In this way we have k-contracted G into a graph G with α(G ) ≤ |I | -k + 1 + |I | ≤ |I | + |I | -d = α(G) -d.
So, (G, k) is a yes-instance in this case as well.

If k ≤ d+1, we consider all possible sequences of at most k edge contractions. This takes time O(|E(G)| k ), which is polynomial as d, and consequently k, is fixed. For every such sequence we check in polynomial time whether the resulting graph has chromatic number at most χ(G) -d. As split graphs are closed under edge contraction and moreover are chordal graphs, the latter can be verified in linear time (see [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF]).

Now let π = χ. Let (G, k) be an instance of d-Contraction Blocker(χ) where G = (V, E) is a split graph. Case 1. χ(G) ≤ d. For (G, k) to be a yes-instance, G must be contracted into a graph G with χ(G ) ≤ χ(G) -d ≤ 0.
The only graph with chromatic number at most 0, is the empty graph. However, a non-empty graph cannot be contracted to an empty graph. Hence, (G, k) is a no-instance in this case.

Case 2. χ(G) = d + 1.
For (G, k) to be a yes-instance, G must be contracted into a graph G with χ(G ) ≤ χ(G) -d = 1. Hence, every connected component of G must consist of exactly one vertex. If G has no connected components with edges, then (G, k) is a yes-instance. Otherwise, because G is a split graph, G has exactly one connected component D containing one or more edges. In that case, (G, k) is a yes-instance if and only if k ≥ |V (D)| -1; this can be checked in constant time.

Case 3. χ(G) ≥ d + 2.
First, assume that k < d. Because every edge contraction reduces the chromatic number by at most 1, (G, k) is a no-instance.

Second, assume that k = d. We consider all possible sequences of at most k edge contractions. This takes time O(|E(G)| k ), which is polynomial as d, and consequently k, is fixed. For every such sequence we check in polynomial time whether the resulting graph has chromatic number at most χ(G) -d. As split graphs are closed under edge contractions and moreover are chordal graphs, the latter can be verified in polynomial time (see [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF]).

Third, assume that k > d. We claim that (G, k) is a yes-instance. This can be seen as follows. Let (K, I) be a maximal split partition of G.

If k < |K|, then we contract k arbitrary edges of K. The resulting graph G has a split partition (K , I)

with |K | = |K| -k ≤ |K| -d -1. Hence χ(G ) ≤ |K | + 1 ≤ |K| -d = χ(G) -d.
Note that the latter equality follows from our assumption that (K, I) is maximal. Now suppose that k ≥ |K|. We contract |K| arbitrary edges of K. The resulting graph G has chromatic number 2 ≤ χ(G) -d. Hence, in both cases, we conclude that (G, k) is a yes-instance.

Finally consider π = ω. We use the previous result combined with the fact that split graphs are perfect and closed under edge contractions.

In our next theorem we give two hardness results which, as explained in Section 1, show that Theorem 3 can be seen as best possible. In their proofs we will reduce from the Red-Blue Dominating Set problem. This problem takes as input a bipartite graph G = (R ∪ B, E) and an integer k, and asks whether there exists a red-blue dominating set of size at most k, that is, a subset D ⊆ B of at most k vertices such that every vertex in R has at least one neighbor in D. This problem is NP-complete, because it is equivalent to the NP-complete problems Set Cover and Hitting Set [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. The Red-Blue Dominating Set problem is also W [START_REF] Alekseev | On easy and hard hereditary classes of graphs with respect to the independent set problem[END_REF]-complete when parameterized by |B| -k [START_REF] Gutin | Kernels for Below-Upper-Bound Parameterizations of the Hitting Set and Directed Dominating Set Problems[END_REF]. Belmonte et al. [START_REF] Belmonte | Parameterized complexity of three edge contraction problems with degree constraints[END_REF] reduced from the same problem for showing that 1-Contraction Blocker(∆) is NP-complete and W[2]-hard (with parameter k) for split graphs, but the arguments we use to prove our results are quite different from the ones they used. Theorem 4. For π ∈ {α, χ, ω}, the Contraction Blocker(π) problem, restricted to split graphs, is NP-complete as well as W[1]-hard when parameterized by d.

Proof. The problem is readily seen to be in NP for π ∈ {α, χ, ω}. Recall that we reduce from Red Blue Dominating Set in order to show NP-hardness and W[1]-hardness with parameter d.

First consider π = α. Let G = (R ∪ B, E) be a bipartite graph that together with an integer k forms an instance of Red-Blue Dominating Set. We may assume without loss of generality that k ≤ |B|. Moreover, we may assume that every vertex of R is adjacent to at least one vertex of B. We add all possible edges between vertices in R. This yields a split graph G * with a split partition (R, B).

Because every vertex in R is assumed to be adjacent to at least one vertex of B in G, we find that (R, B) is a minimal split partition of G * .

Because Red-Blue Dominating Set problem is NP-complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] and W [START_REF] Alekseev | On easy and hard hereditary classes of graphs with respect to the independent set problem[END_REF]-complete when parameterized by |B| -k [START_REF] Gutin | Kernels for Below-Upper-Bound Parameterizations of the Hitting Set and Directed Dominating Set Problems[END_REF], it suffices to prove that G has a red-blue dominating set of size at most k if and only if (G * , |B| -k) is a yes-instance of (|B| -k)-Contraction Blocker(α). We prove this claim below.

First suppose that G has a red-blue dominating set D of size at most k. Because k ≤ |B|, we may assume without loss of generality that |D| = k (otherwise we would just add some vertices from B \ D to D).

In G * we contract every u ∈ B \ D onto a neighbor in R. In this way we (|B| -k)-contracted G * into a graph G . Note that G is a split graph that has a split partition (R, D). Because every vertex in R is adjacent to at least one vertex of D in G by definition of D, it is adjacent to at least one vertex of D in G * . The latter statement is still true for G , as contracting an edge incident to a vertex u ∈ B is equivalent to deleting u. Hence, (R, D) is a minimal split partition of

G , so α(G ) = |D|. Because (R, B) is a minimal split partition of G * , we have α(G * ) = |B|. This means that α(G ) = |D| = |B|-(|B|-|D|) = α(G * )-(|B|-k). We conclude that (G * , |B| -k) is a yes-instance of (|B| -k)-Contraction Blocker(α). Now suppose that (G * , |B| -k) is a yes-instance of (|B| -k)-Blocker(α), that is, G * can be (|B| -k)-contracted into a graph G such that α(G ) ≤ α(G * ) -(|B| -k). Recall that α(G * ) = |B|. Hence, α(G ) ≤ k.
Let p be the number of contractions of edges with one end-vertex in B. Note that any such contraction decreases the size of the independent set B by exactly one. If p < |B| -k, then G contains an independent set of size |B| -p > k, which would mean that α(G ) > k, a contradiction. Hence, p ≥ |B| -k, which implies that p = |B| -k as we performed no more than |B| -k contractions in total. Let D denote the independent set obtained from B after all edge contractions. Then we find that k

= |B| -(|B| -k) = |B| -p = |D| ≤ α(G ) ≤ α(G * ) -(|B| -k) = |B| -(|B| -k) = k. Hence, |D| = α(G ),
which means that (D, R) is a minimal split partition of G . This means that every vertex of R is adjacent to at least one vertex of D in G . Because all our contractions were performed on edges with one end-vertex in B, we have only removed vertices from G * , that is, G is an induced subgraph of G * . Hence, every vertex of R is adjacent to at least one vertex of D in G . Consequently, D is a red-blue dominating set of G with size |D| = k.

We omit the proof for π = χ. As split graphs are perfect and closed under edge contractions, the case π = ω follows directly from the case π = χ.

Conclusions

Because split graphs are (2P 2 , C 4 , C 5 )-free [START_REF] Földes | Split graphs, 8th South-Eastern[END_REF], they are P 5 -free. This means that Theorem 2, combined with Theorem 4, has the following consequence.

Corollary 1. Let π ∈ {α, χ, ω). Then Contraction Blocker(π) restricted to P -free graphs is polynomial-time solvable if ≤ 4 and NP-complete if ≥ 5.

Recently, Lokshtanov, Vatshelle, and Villanger [START_REF] Lokshtanov | Independent Set in P5-Free Graphs in Polynomial Time[END_REF] proved that the independence number of a P 5 -free graph can be computed polynomial time (thereby solving a long-standing open problem). In contrast, already 1-Contraction Blocker(α) is NP-complete for P 5 -free graphs (recall that it is NP-complete even for cobipartite graphs, as explained in Section 1). The problems of determining the chromatic number [START_REF] Král | Complexity of coloring graphs without forbidden induced subgraphs[END_REF] and the clique number [START_REF] Alekseev | On easy and hard hereditary classes of graphs with respect to the independent set problem[END_REF] are NP-hard for P 5 -free graphs. One might be able to use these two results to prove NP-hardness of d-Contraction Blocker(π) for π ∈ {χ, ω} and d ≥ 1.

The classes of cographs and split graphs are subclasses of the class of perfect graphs. Thus, it is interesting to study Contraction Blocker(π) for other subclasses of perfect graphs, such as interval graphs or cobipartite graphs with π ∈ {α, χ} (since for perfect graphs Contraction Blocker(ω) and Contraction Blocker(χ) are equivalent). For interval graphs we can show the following result.

Theorem 5 (♠). Let π ∈ {χ, ω}. Then Contraction Blocker(π) can be solved in polynomial time on interval graphs.

Whether the same result holds for Contraction Blocker(α) is not clear and left as future work.

Cobipartite graphs have independence number at most 2, that is, are 3P 1free. We can show the following.

Theorem 6 (♠). For any fixed d ≥ 0, the d-Contraction Blocker(χ) problem can be solved in polynomial time on 3P 1 -free graphs.

Whether Theorem 6 can be generalized to the class of 4P 1 -free graphs is an open problem. Its proof cannot be translated to 4P 1 -free graphs, because computing the chromatic number is NP-hard for 4P 1 -free graphs [START_REF] Král | Complexity of coloring graphs without forbidden induced subgraphs[END_REF]. Also, determining the complexity of Contraction Blocker(χ) for the class of cobipartite graphs and its superclass of 3P 1 -free graphs is still open. Moreover, we do not know the complexity of d-Contraction Blocker(ω) for 3P 1 -free graphs and d ≥ 1 (whereas, for π = α this problem is NP-complete already for d = 1 even for cobipartite graphs, as we recalled earlier).

Finally, we note that a similar table as Table 1 is not complete for the other variants of the blocker problem where the operation permitted is the edge addition, edge deletion or vertex deletion, respectively. For edge deletions the problem, for π = χ, is known [START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF] to be NP-hard for general graphs even if d = 1, polynomial-time solvable on threshold graphs (which form a proper subclass of P 4 -free graphs) if d is part of the input and polynomial-time solvable on split graphs but only if d is fixed. For edge additions the problem, for π = α, is known [START_REF] Bazgan | Blockers for the stability number and the chromatic number[END_REF] to be NP-hard for general graphs even if d = 1 and polynomial-time solvable on split graphs if d is fixed. For vertex deletions the problem, for π = ω, is known to be NP-complete for general graphs [START_REF] Pajouh | Minimum vertex blocker clique problem[END_REF] and, for π = α, polynomialtime solvable for cographs if d is part of the input [START_REF] Bazgan | The most vital nodes with respect to independent set and vertex cover[END_REF]. It would be interesting to complete these results in the way we have done for edge contractions.

  S e yz be the the set of contractions of edges with one end-vertex in G y and the other one in G z . Let a y = |S e y | and let a z = |S e z |. Then |S e yz | = i -a y -a z . Let S v y and S v z be the set of deletions of vertices in G y and G z , respectively. Let b = |S v y |. Then |S v z | = j -b. We distinguish between two cases.

Theorem 3 .

 3 Let π ∈ {α, χ, ω}. For any fixed d ≥ 0, the d-Contraction Blocker(π) problem is polynomial-time solvable on split graphs. Proof. First consider π = α. Let (G, k) be an instance of d-Contraction Blocker(α) where G = (V, E) is a split graph. Let (K, I) be a minimal split partition of G. Let I be the set of vertices in I that have at least one neighbor in K, and let I = I \ I . Because G is a split graph, all vertices of I belong to the same connected component D of G. Moreover, we have α(G) = |I| = |I | + |I | = α(D) + |I |. First suppose that |I | ≤ d. For (G, k) to be a yes-instance, G must be contracted into a graph G with α(G ) ≤ α(G) -d = |I | + |I | -d ≤ |I |. This means that we must contract D into the empty graph, which is not possible. Hence, (G, k) is a no-instance in this case. Hence, we may assume without loss of generality that |I | ≥ d + 1. Suppose that k ≥ d + 1. If k ≥ |I |, then we contract every vertex of I onto a neighbor in K. In this way we have k

Table 1 .

 1 Our results from Sections 3 and 4 for Contraction Blocker(π) with π ∈ {α, χ, ω} (recall that, when d is fixed, we denote the problem by d-Contraction Blocker(π)). Here, NP-c stands for NP-complete.

		general graphs cographs	split graphs
	d fixed	NP-c even if d = 1	P	P
	d part of input	NP-c	P	NP-c and W[1]-hard with parameter d

We omitted the proofs of some results due to space constraints. These results are marked by ♠.

For a cograph G, compute T G and use the formula α(Gx) = α(Gy) + α(Gz) if x is a ⊕-node with children y and z and α(Gx) = max{α(Gy), α(Gz)} otherwise. Alternatively, see for example[START_REF] Chvátal | Four classes of perfectly orderable graphs[END_REF] for a linear-time algorithm on a superclass of cographs.

Author supported partially by Marie Curie International Reintegration Grant PIRG07/GA/2010/268322. Author supported by EPSRC EP/K025090/1.