Petr A Golovach

Pinar Heggernes

Pim Van 't Hof
email: pim.vanthof@ii.uib.no@ii.uib.no

Christophe Paul
email: paul@lirmm.fr

Hadwiger Number of Graphs with Small Chordality *

The Hadwiger number of a graph G is the largest integer h such that G has the complete graph K h as a minor. We show that the problem of determining the Hadwiger number of a graph is NP-hard on co-bipartite graphs, but can be solved in polynomial time on cographs and on bipartite permutation graphs. We also consider a natural generalization of this problem that asks for the largest integer h such that G has a minor with h vertices and diameter at most s. We show that this problem can be solved in polynomial time on AT-free graphs when s ≥ 2, but is NP-hard on chordal graphs for every fixed s ≥ 2.

Introduction

The Hadwiger number of a graph G, denoted by h(G), is the largest integer h such that the complete graph K h is a minor of G. The Hadwiger number has been the subject of intensive study, not in the least due to a famous conjecture by Hugo Hadwiger from 1943 [START_REF] Hadwiger | Über eine klassifikation der streckenkomplexe[END_REF] stating that the Hadwiger number of any graph is greater than or equal to its chromatic number. In a 1980 paper, Bollobás, Catlin, and Erdős [2] called Hadwiger's conjecture "one of the deepest unsolved problems in graph theory." Despite many partial results the conjecture remains wide open more than 70 years after it first appeared in the literature.

Given the vast amount of graph-theoretic results involving the Hadwiger number, it is natural to study the computational complexity of the Hadwiger Number problem, which is to decide, given an n-vertex graph G and an integer h, whether the Hadwiger number of G is greater than or equal to h (or, equivalently, whether G has K h as a minor). Rather surprisingly, it was not until 2009 that this problem was shown to be NP-complete by Eppstein [START_REF] Eppstein | Finding large clique minors is hard[END_REF]. Two years earlier, Alon, Lingas, and Wahlén [1] observed that the problem is fixedparameter tractable when parameterized by h due to deep results by Robertson and Seymour [17]. This shows that the problem of determining the Hadwiger number of a graph is in some sense easier than the closely related problem of determining the clique number of a graph, as the decision version of the latter problem is W [1]-hard when parameterized by the size of the clique. Alon et al. [1] showed that the same holds from an approximation point of view: they provided a polynomial-time approximation algorithm for the Hadwiger Number problem with approximation ratio O( √ n), contrasting the fact that it is NP-hard to approximate the clique number of an n-vertex graph in polynomial time to within a factor better than n 1-for any > 0 [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF].

Bollobás, Catlin, and Erdős [2] referred to the Hadwiger number as the contraction clique number. This is motivated by the observation that for any integer h, a connected graph G has K h as a minor if and only if G has K h as a contraction. In this context, it is worth mentioning another problem that has recently attracted some attention from the parameterized complexity community. The Clique Contraction problem takes as input an n-vertex graph G and an integer k, and asks whether G can be modified into a complete graph by a sequence of at most k edge contractions. Since every edge contraction reduces the number of vertices by exactly 1, it holds that (G, k) is a yes-instance of the Clique Contraction problem if and only if G has the complete graph K n-k as a contraction (or, equivalently, as a minor). Therefore, the Clique Contraction problem can be seen as the parametric dual of the Hadwiger Number problem, and is NP-complete on general graphs. When parameterized by k, the Clique Contraction problem was recently shown to be fixed-parameter tractable [START_REF] Cai | Contracting few edges to remove forbidden induced subgraphs[END_REF][START_REF] Lokshtanov | On the hardness of eliminating small induced subgraphs by contracting edges[END_REF], but the problem does not admit a polynomial kernel unless NP ⊆ coNP/ poly [START_REF] Cai | Contracting few edges to remove forbidden induced subgraphs[END_REF].

In this paper, we study the computational complexity of the Hadwiger Number problem on several graph classes of bounded chordality. For chordal graphs, which form an important subclass of 4-chordal graphs, the Hadwiger Number problem is easily seen to be equivalent to the problem of finding a maximum clique, and can therefore be solved in linear time on this class [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF]. In Section 3, we present polynomial-time algorithms for solving the Hadwiger Number problem on two other well-known subclasses of 4-chordal graphs: cographs and bipartite permutation graphs. We also prove that the problem remains NP-complete on co-bipartite graphs, and hence on 4-chordal graphs. The latter result implies that the problem is also NP-complete on AT-free graphs, a common superclass of cographs and bipartite permutation graphs.

In Section 4, we consider a natural generalization of the Hadwiger Number

problem, and provide additional results about finding large minors of bounded diameter. We show that the problem of determining the largest integer h such that a graph G has a minor with h vertices and diameter at most s can be solved in polynomial time on AT-free graphs if s ≥ 2. In contrast, we show that this problem is NP-hard on chordal graphs for every fixed s ≥ 2, and remains NP-hard for s = 2 even when restricted to split graphs. Observe that when s = 1, the problem is equivalent to the Hadwiger Number problem and thus NP-hard on AT-free graphs and linear-time solvable on chordal graphs due to our aforementioned results.

Preliminaries

We consider finite undirected graphs without loops or multiple edges. For each of the graph problems considered in this paper, we let n = |V (G)| and m = |E(G)| denote the number of vertices and edges, respectively, of the input graph G.

For a graph G and a subset U ⊆ V (G) of vertices, we write G[U ] to denote the subgraph of G induced by U . We write G-U to denote the subgraph of G induced by V (G) \ U , and G -u if U = {u}. For a vertex v, we denote by N G (v) the set of vertices that are adjacent to v in G. The distance dist G (u, v) between vertices u and v of G is the number of edges on a shortest path between them. The

diameter diam(G) of G is max{dist G (u, v) | u, v ∈ V (G)}.
The complement of G is the graph G with vertex set V (G), where two distinct vertices are adjacent in G if and only if they are not adjacent in G. For two disjoint vertex sets X, Y ⊆ V (G), we say that X and Y are adjacent if there are x ∈ X and y ∈ Y that are adjacent in G.

We say that P is a (u, v)-path if P is a path that joins u and v. The vertices of P different from u and v are the inner vertices of P . We denote by P n and C n the path and the cycle on n vertices respectively. The length of a path is the number of edges in the path. A set of pairwise adjacent vertices is a clique. A matching is a set M of edges such that no two edges in M share an end-vertex. A vertex incident to an edge of a matching M is said to be saturated by M . We write K n to denote the complete graph on n vertices, i.e., graph whose vertex set is a clique. For two integers a ≤ b, the (integer

) interval [a, b] is defined as [a, b] = {i ∈ Z | a ≤ i ≤ b}. If a > b, then [a, b] = ∅. The chordality chord(G) of a graph G is the length of a longest induced cycle in G; if G has no cycles, then chord(G) = 0. For a non-negative integer k, a graph G is k-chordal if chord(G) ≤ k. A graph is chordal if it is 3-chordal. A graph is chordal bipartite if it
is both 4-chordal and bipartite. A graph is a split graph if its vertex set can be partitioned in an independent set and a clique. For a graph F , we say that a graph G is F -free if G does not contain F as an induced subgraph. A graph is a cograph if it is P 4 -free. Let σ be a permutation of {1, . . . , n}. A graph G is said to be a permutation graph for σ if G has vertex set {1, . . . , n} and two vertices i, j are adjacent if and only if i, j are reversed by the permutation. A graph G is a permutation graph if G is a permutation graph for some σ. A graph is a bipartite permutation graph if it is bipartite and permutation. An asteroidal triple (AT) is a set of three non-adjacent vertices such that between each pair of them there is a path that does not contain a neighbor of the third. A graph is AT-free if it contains no AT. Each of the above-mentioned graph classes can be recognized in polynomial (in most cases linear) time, and they are closed under taking induced subgraphs [START_REF] Brandstädt | Graph Classes: A Survey[END_REF]12]. See the monographs by Brandstädt et al. [START_REF] Brandstädt | Graph Classes: A Survey[END_REF] and Golumbic [12] for more properties and characterizations of these classes and their inclusion relationships.

Minors, Induced Minors, and Contractions. Let G be a graph and let e ∈ E(G). The contraction of e removes both end-vertices of e and replaces them by a new vertex adjacent to precisely those vertices to which the two endvertices were adjacent. We denote by G/e the graph obtained from G be the contraction of e. For a set of edges S, G/S is the graph obtained from G by the contraction of all edges of S.

A graph H is a contraction of G if H = G/S for some S ⊆ E(G). We say that G is k-contractible to H if H = G/S for some set S ⊆ E(G) with |S| ≤ k. A graph H is an induced minor of G if a H is a contraction of an induced subgraph of G. Equivalently, H is an induced minor of G if H can be obtained from G by a sequence of vertex deletions and edge contractions. A graph H is a minor of a graph G if H is a contraction of a subgraph of G.
Equivalently, H is a minor of G if H can be obtained from G by a sequence of vertex deletions, edge deletions, and edge contractions.

Let G and H be two graphs. An H-witness structure W of G is a partition {W (x) | x ∈ V (H)} of the vertex set of a (not necessarily proper) subgraph of G into |V (H)| sets called bags, such that the following two conditions hold:

(i) each bag W (x) induces a connected subgraph of G;

(ii) for all x, y ∈ V (H) with xy ∈ E(H), bags W (x) and W (y) are adjacent in G.

In addition, we may require an H-witness structure to satisfy one or both of the following additional conditions:

(iii) for all x, y ∈ V (H) with xy / ∈ E(H), bags W (x) and W (y) are not adjacent in G;

(iv) every vertex of G belongs to some bag.

By contracting each of the bags into a single vertex we observe that H is a contraction, an induced minor, or a minor of G if and only if G has an H-witness structure W that satisfies conditions (i)-(iv), (i)-(iii), or (i)-(ii), respectively. We will refer to such a structure W as an H-contraction structure, an H-induced minor structure, and an H-minor structure, respectively. Observe that, in general, such a structure W is not uniquely defined.

Let W be an H-witness structure of G, and let W (x) be a bag of W. We say that W

(x) is a singleton if |W (x)| = 1 and W (x) is an edge-bag if |W (x)| = 2. We say that W (x) is a big bag if |W (x)| ≥ 2.
We conclude this section by presenting four structural lemmas that will be used in the polynomial-time algorithms presented in Section 3. The first lemma is due to Heggernes et al. [START_REF] Heggernes | Contracting graphs to paths and trees[END_REF].

Lemma 1 ([15]

). If a graph G is k-contractible to a graph H, then any Hcontraction structure W of G satisfies the following properties:

• W has at most k big bags;

• each bag of W contains at most k + 1 vertices;

• all the big bags of W together contain at most 2k vertices.

The next lemma readily follows from the definitions of a minor, an induced minor, and a contraction. Lemma 2. For every connected graph G and non-negative integer p, the following statements are equivalent:

• G has K p as a contraction;

• G has K p as an induced minor;

• G has K p as a minor.

We say that an H-induced minor structure

W = {W (x) | x ∈ V (H)} is minimal if there is no H-induced minor structure W = {W (x) | x ∈ V (H)} with W (x) ⊆ W (x)
for every x ∈ V (H) such that at least one inclusion is proper.

Lemma 3. For any minimal K p -induced minor structure of a graph G, each bag induces a subgraph of diameter at most max{chord(G) -3, 0}.

Proof. Let W be a minimal K p -induced minor structure of G. Since K p is a complete graph, any two bags of W are adjacent. Let W (x) be a bag. If |W (x)| = 1, then diam(G[W (x)]) = 0 and the statement holds. Observe that if p ≤ 2, then each bag of W is a singleton due to the minimality of W. Suppose that |W (x)| ≥ 2 and p ≥ 3.

Let u, v ∈ W (x) be vertices such that dist G[W (x)] (u, v) = diam(G[W (x)]). Let P be a shortest (u, v)-path in G[W (x)].
Observe that by the choice of u and v, the graphs G[W (x)] -u and G[W (x)] -v are connected. Because W is minimal, there are two bags W (y) and W (z) for distinct y, z ∈ V (H) such that u is the unique vertex of W (x) adjacent to a vertex of W (y) and v is the unique vertex of W (x) adjacent to a vertex of W (z). Because the graphs G[W (y)] and G[W (z)] are connected and the sets W (y) and W (z) are adjacent, there is an induced (u, v)-path P in G whose inner vertices all belong to W (y) ∪ W (z). Notice that P has length at least 3 and no inner vertex of P is adjacent to a vertex of W (x) in G. Consequently, the union of P and P is an induced cycle of length at least diam(G[W (x)]) + 3 ≤ chord(G), so we conclude that diam(G[W (x)]) ≤ chord(G) -3.

Note that Lemma 3 immediately implies the aforementioned equivalence on chordal graphs between the Hadwiger Number problem and the problem of finding a maximum clique. Lemma 3 also implies the following result.

Corollary 1. If G is a graph of chordality at most 4, then for any minimal K p -induced minor structure in G, each bag is a clique.

We say that a K p -induced minor structure is nice if each bag is either a singleton or an edge-bag.

Lemma 4. Let G be a C 6 -free graph of chordality at most 4. If K p is an induced minor of G, then G has a nice K p -induced minor structure.

Proof. Let W be a minimal K p -induced minor structure in G. By Corollary 1, each bag of W is a clique. Hence, in order to prove the lemma, it suffices to show that each bag contains at most two vertices.

For contradiction, suppose there exists a bag W (x) that contains at least three distinct vertices u 1 , u 2 , u 3 . Notice that because W (x) is a clique, for any u i ∈ W (x), G[W (x)] -u i is connected. Because W is minimal, there are 3 bags W (y 1 ), W (y 2 ) and W (y 3 ) for distinct y 1 , y 2 , y 3 ∈ V (H) such that u i is the unique vertex of W (x) adjacent to a vertex of W (y i ) for i ∈ {1, 2, 3}. For any distinct i, j ∈ {1, 2, 3}, there is an induced (u i , u j )-path P ij in G whose inner vertices all belong to W (y i ) ∪ W (y j ), because the graphs G[W (y i )] and G[W (y j )] are connected and the sets W (y i ) and W (y j ) are adjacent. Since W (x) is a clique and G has chordality at most 4, path P ij has length 3.

Let

P 12 = u 1 v 1 w 2 u 2 , P 23 = u 2 v 2 w 3 u 3 and P 31 = u 3 v 3 w 1 u 1 .
We select the paths P ij for i, j ∈ {1, 2, 3} in such a way that they have the maximum number of common edges. We claim that any two distinct paths have a common edge.

Notice that v i , w i ∈ W (y i ) and if v i = w i , then v i w i ∈ E(G) because each W (y i ) is a clique by Corollary 1. Suppose that for some index i ∈ {1, 2, 3},

say for i = 1, v i = w i . Consider the cycle u 1 u 2 v 2 w 3 v 3 w 1 u 1 if v 3 = w 3 and the cycle u 1 u 2 v 2 v 3 w 1 u 1 if v 3 = w 3 .
Because G has chordality at most 4, these cycles are not induced. Since u 1 , u 2 are not adjacent to v 3 , w 3 , it implies that v 2 w 1 ∈ E(G). Then the path P 12 could be replaced by u 1 w 1 v 2 u 2 and we would get more common edges in the paths. Therefore, v i = w i for i ∈ {1, 2, 3}.

It remains to observe that

G[{u 1 , u 2 , u 3 , v 1 , v 2 , v 3 }] is isomorphic to C 6 .

Computing the Hadwiger Number

In this section we show that Hadwiger Number problem can be solved in polynomial time on cographs and bipartite permutation graphs. We complement these results by showing that the problem is NP-complete on co-bipartite graphs, another well-known subclass of the class of 4-chordal graphs.

Hadwiger number of cographs

We need some additional terminology.

Let G 1 and G 2 be two graphs with

V (G 1 ) ∩ V (G 2 ) = ∅. The (disjoint) union of G 1 and G 2 is defined as G 1 ⊕ G 2 = (V (G 1 ) ∪ V (G 2 ), E(G 1 ) ∪ E(G 2 )),
and the join of G 1 and G 2 is defined as

G 2 ⊗ G 2 = (V (G 1 ) ∪ V (G 2 ), E(G 1 ) ∪ E(G 2 ) ∪ {uv | u ∈ V (G 1 ), v ∈ V (G 2 )}).
It is well-known (see, e.g., [START_REF] Brandstädt | Graph Classes: A Survey[END_REF]12]) that every cograph can be constructed recursively from isolated vertices using these two operations. Equivalently, cographs can be defined as follows. A cotree T of a cograph G is a rooted tree with two types of interior nodes: 0-nodes (corresponding to disjoint unions) and 1-nodes (corresponding to joins). The vertices of G are assigned to the leaves of T in a one-to-one manner. Two vertices u and v are adjacent in G if and only if the lowest common ancestor of the leaves u and v in T is a 1-node. A graph is a cograph if and only if it has a cotree [START_REF] Corneil | Complement reducible graphs[END_REF]. Cographs can be recognized and their corresponding cotrees can be generated in linear time [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF][START_REF] Habib | A simple linear time algorithm for cograph recognition[END_REF]. Proof. Let G be a cograph on n vertices. We may assume that G is connected, as otherwise we can simply consider the connected components of G one by one. By Lemma 2, it is sufficient to find the maximum p such that K p is an induced minor of G. Because cographs are C 6 -free, we can use Lemma 4.

For a non-negative integer r, denote by c r (G) the largest integer p such that G has a nice K p -induced minor structure with exactly r edge-bags. If G has no such structure for any p, then c r (G) = 0. Notice that c 0 (G) is the size of a maximum clique in G.

If G has one vertex, then c r (G) = 1 if r = 0 and c r (G) = 0 otherwise. It is also straightforward to see that

c r (G 1 ⊕ G 2 ) = max{c r (G 1 ), c r (G 2 )},
for any two disjoint graphs G 1 and G 2 .

We need the following observation about joins.

Claim 1. Let G 1 and G 2 be disjoint graphs, and suppose that

G = G 1 ⊗ G 2 has a nice K p -induced minor structure with r > 0 edge-bags. Then G has a K p - induced minor structure W = {W (x) | x ∈ V (K p )} with r edge-bags such that either |V (G 1 ) ∩ W (x)| ≤ 1 for every edge-bag W (x) ∈ W, or |V (G 2 ) ∩ W (x)| ≤ 1 for every edge-bag W (x) ∈ W. Proof of Claim 1. Let W = {W (x) | x ∈ V (K p )} be a nice K p -induced minor structure in G that has r edge-bags. Suppose that W (x) = {u 1 , v 1 } for u 1 , v 1 ∈ V (G 1 ) and W (y) = {u 2 , v 2 } for u 2 , v 2 ∈ V (G 2 ). Because G = G 1 ⊗ G 2 , the set {u 1 , v 1 , u 2 , v 2 } induces K 4 . We replace W (x) and W (y) by W (x) = {u 1 , u 2 } and W (y) = {v 1 , v 2 }. Because u 1 , v 1 are adjacent to the vertices of G 2 and u 2 , v 2
are adjacent to the vertices of G 1 , the bags W (x) and W (y) are adjacent to every bag W (z) for z = x, y. Therefore, we obtain a new nice K p -induced minor structure with r edge-bags. By doing such replacement recursively, we obtain a nice K p -induced minor structure with the desired property. This completes the proof of Claim 1.

Now we obtain the formula for

c r (G 1 ⊗ G 2 ). Claim 2. Let G 1 and G 2 be disjoint graphs, n 1 = |V (G 1 )| and n 2 = |V (G 2 )|,
and let r be a non-negative integer. For a non-negative integer s ≤ r and i = 1, 2, let

c s,i = s + min{c r-s (G i ), n i -r} + min{n 3-i -s, c 0 (G 3-i )} if n i -2r + s ≥ 0, 0 if n i -2r + s < 0. Then c r (G 1 ⊗ G 2 ) = max{c s,i | 0 ≤ s ≤ min{n 1 , n 2 , r}, 1 ≤ i ≤ 2}. Proof of Claim 2. Let G = G 1 ⊗ G 2 . Let p = c r (G) > 0 and let W = {W (x) | x ∈ V (K p )} be a nice K p -induced minor structure in G that has r edge-bags. Let W (1) 1 = {W (x) | W (x) = {u}, u ∈ V (G 1 )}, W (2) 1
= {W (x) | W (x) = {u, v}, u, v ∈ V (G 1 )}, W (1) 2 = {W (x) | W (x) = {u}, u ∈ V (G 2 )}, W (2) 2 = {W (x) | W (x) = {u, v}, u, v ∈ V (G 2 )}, and W 3 = {W (x) | W (x) = {u, v}, u ∈ V (G 1 ), v ∈ V (G 2 )}. By Claim 1, we can assume that W (2) 1 = ∅ or W (2) 2 = ∅. Suppose that W (2) 2 = ∅; the case W (1) 1 = ∅ is symmetric. Let s = |W 3 |. Clearly, s ≤ min{n 1 , n 2 , r}. The set W (2)
1 has r -s edge-bags, and these bags are disjoint with the bags of W 3 . Because each bag of are disjoint with the bags of

W 3 has one vertex in V (G 1 ), it holds that 2(r -s) + s ≤ n 1 . Hence, c s,1 = s + min{c r-s (G 1 ), n 1 -r} + min{n 2 -s, c 0 (G 2 )}. Observe that |W (1) 1 | + |W (2) 1 | ≤ c r-s (G 1 ). Also because the bags of W (1) 1 , W (2) 1 and W 3 are disjoint sets, |W (1) 1 | + 2|W (2) 1 | + s ≤ n 1 . We have that n 1 ≥ |W (1) 1 | + 2|W (2) 1 | + s = |W (1) 1 | + |W (2) 1 | + (r -s) + s and |W (1) 1 | + |W (2) 1 | ≤ n 1 -r. Clearly, |W (1) 2 | ≤ c 0 (G 2 ),
W 3 , |W (1) 2 | + s ≤ n 2 . Therefore, |W (1) 2 | ≤ min{n 2 -s, c 0 (G 2 )}. We have that p = |W (1) 1 | + |W (2) 1 | + |W (1) 2 | + |W 3 | ≤ s + min{c r-s (G 1 ), n 1 -r} + min{n 2 - s, c 0 (G 2 )} = c s,1 . We conclude that c r (G) ≤ max{c s,i | 0 ≤ s ≤ min{n 1 , n 2 , r}, 1 ≤ i ≤ 2}. For the other direction, let 0 ≤ s ≤ min{n 1 , n 2 , r} and assume that c s,1 ≥ c s,2 (the other case is symmetric). Let K be a maximum clique in G 2 . Recall that c 0 (G 2 ) = |K|.
If c s,1 = 0, then it is trivial to see that c r (G) ≥ c s,1 . Assume that c s,1 > 0. Then n 1 -2r + s ≥ 0. Let W 1 be a nice K q -induced minor structure in G 1 with r -s edge-bags for q = c r-s (G 1 ).

Suppose that c r-s (G 1 ) ≤ n 1 -r, i.e., min{c r-s (G 1 ), n 1 -r} = c r-s (G 1 ). We select a set R 1 of s vertices in V (G 1 ) such that the vertices of R 1 are not included in the bags of W 1 . We always can do it because the bags of

W 1 contain c r-s (G 1 )+r-s ≤ n 1 -s vertices of G 1 . Let R 2 be a set of s vertices in V (G 2 ) such that R 2 ∩K
has minimum size. We consider a nice K p -induced minor structure in G that has s edge-bags containing pairs of vertices {u, v} for u ∈ R 1 and v ∈ R 2 , r -s edge-bags that are edge-bags of W 1 , the singletons of W 1 , and

|K \ R 2 | singletons {v} for v ∈ K \R 2 . Here p = s+c r-s (G 1 )+|K \R 2 |. If c 0 (G 2 ) ≤ n 2 -s, then |K \ R 2 | = c 0 (G 2 ). If c 0 (G 2 ) ≥ n 2 -s, then |K \ R 2 | = n 2 -s. Then c r (G) ≥ p = s + c r-s (G 1 ) + |K \ R 2 | ≥ s + min{c r-s (G 1 ), n 1 -r} + min{n 2 -s, c 0 (G 2 )}.
Finally, assume that c r-s (G 1 ) > n 1 -r, i.e., min{c r-s (G 1 ), n 1 -r} = n 1 -r. Let S be the set of vertices u ∈ V (G 1 ) such that {u} is a singleton in W. We select a set R 1 of s vertices in V (G 1 ) such that the vertices of R 1 are not included in the edge-bags of W 1 and R 1 ∩ S has minimum size. We can find such a set

R 1 because W 1 has 2(r -s) ≤ n 1 -s vertices in the edge-bags. Because the total number of vertices of G 1 in the bags of W 1 is c r-s (G 1 ) + r -s > n 1 -s, R 1 ∩ S = ∅. Also, |S \ R 1 | = n 1 -2(r -s) -s = n 1 -2r + s. Let R 2 be a set of s vertices in V (G 2 ) such that R 2 ∩ K has minimum size. We consider a nice K p -induced minor structure in G that has s edge-bags containing pairs of vertices {u, v} such that u ∈ R 1 and v ∈ R 2 , r -s edge-bags that are edge- bags of W 1 , |S \ R 1 | singletons {u} such that {u} ∈ W 1 and u ∈ S \ R 1 , and |K \ R 2 | singletons {v} such that v ∈ K \ R 2 . Here p = r + |S \ R 1 | + |K \ R 2 |. Then c r (G) ≥ p = r + |S \ R 1 | + |K \ R 2 | = r + (n 1 -2r + s) + |K \ R 2 | = s + (n 1 -r) + |K \ R 2 | ≥ s + min{c r-s (G 1 ), n 1 -r} + min{n 2 -s, c 0 (G 2 )}.
In all cases c r (G) ≥ c s,1 . By our assumption, c s,1 ≥ c s,2 . Hence,

c r (G) ≥ max{c s,i | 0 ≤ s ≤ min{n 1 , n 2 , r}, i = 1, 2}.
and this completes the proof of Claim 2.

In order to find the maximum p such that K p is an induced minor of G, we first compute a cotree of G, which can be done in linear time [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF][START_REF] Habib | A simple linear time algorithm for cograph recognition[END_REF]. We then compute c r (G) for all r ∈ {0, . . . , n} using the obtained formulas for

c r (G 1 ⊕ G 2 ) and c r (G 1 ⊗ G 2 ) in O(n 3 ) time. Let p = max 0≤r≤n c r (G).
It remains to observe that by Lemma 4, K p is the complete graph of maximum size that is an induced minor of G.

Hadwiger number of bipartite permutation graphs

Let us for a moment consider the class of chordal bipartite graphs. Recall that these are exactly the bipartite graphs that have chordality at most 4. It is wellknown that chordal bipartite graphs form a proper superclass of the class of bipartite permutation graphs. Since chordal bipartite graphs have chordality at most 4 and are C 6 -free due to the absence of triangles, we can apply Lemma 4 to this class. Let us additionally observe that the number of singletons in any K p -induced minor structure of a bipartite graph is at most 2.

The above observations allow us to reduce the Hadwiger Number problem on chordal bipartite graphs to a special matching problem as follows. We say that a matching M in a graph G is a clique-matching if for any two distinct edges e 1 , e 2 ∈ M , there is an edge in G between an end-vertex of e 1 and an end-vertex of e 2 . Now consider the following decision problem: Proof. Suppose that Clique-Matching can be solved in f (n, m) time on chordal bipartite graphs with n vertices and m edges. Let (G, p) be an instance of the Hadwiger Number problem, where G is a chordal bipartite graph with n vertices and m edges. We assume that G is connected, as otherwise we can simply consider the connected components of G one by one.

Clique-Matching

Let V 1 , V 2 be a bipartition of V (G).
By Lemma 2, it holds that (G, p) is a yes-instance if and only if K p is an induced minor of G. Moreover, as a result of Lemma 4, K p is an induced minor of G if and only if G has a nice K p -induced minor structure W. Hence it remains to prove that we can decide in O((n + m) • f (n, m)) time whether such a structure W exists. Recall that any K p -induced minor structure of G has at most two singletons due to the fact that G is bipartite, and that any two bags in such a structure are adjacent.

It is straightforward to see that G has a nice K p -induced minor structure without singletons if and only if G has a clique-matching of size at least p. Hence, the existence of such a structure can be checked by solving Clique-Matching for the instance (G, p) in f (n, m) time.

To verify the existence of a nice K p -induced minor structure with one singleton {u}, we do as follows for every possible candidate vertex

u ∈ V (G). If u ∈ V 1 , then we construct the graph G = G[(V 1 \{u})∪N G (u)], and we construct G = G[(V 2 \ {u}) ∪ N G (u)] if u ∈ V 2 .
We then solve Clique-Matching for the instance (G , p -1).

Finally, to check whether G has a nice K p -induced minor structure with two singletons, we check all edges uv ∈ E(G)

with u ∈ V 1 and v ∈ V 2 . For each such edge uv, we construct G = G[(N G (u) \ {v}) ∪ (N G (v) \ {u})] and solve Clique-Matching for the instance (G , p -2).
It is clear that the total running time is

O((n + m) • f (n, m)).
We will use the following characterization of bipartite permutation graphs given by Spinrad, Brandstädt, and Stewart [START_REF] Spinrad | Bipartite permutation graphs[END_REF] (see also [START_REF] Brandstädt | Graph Classes: A Survey[END_REF]). Let G be a bipartite graph and let V 1 , V 2 be a bipartition of V (G). An ordering of vertices of V 2 has the adjacency property if for every u ∈ V 1 , N G (u) consists of vertices which are consecutive in the ordering of V 2 . An ordering of vertices of V 2 has the enclosure property if for every pair of vertices u

, v ∈ V 1 such that N G (u) ⊆ N G (v), vertices in N G (v) \ N G (u) occur consecutively in the ordering of V 2 .

Lemma 6 ([18]

). Let G be a bipartite graph with bipartition V 1 , V 2 . The graph G is a bipartite permutation graph if and only there is an ordering of V 2 that has the adjacency and enclosure properties. Moreover, bipartite permutation graphs can be recognized and the corresponding ordering of V 2 can be constructed in linear time.

Theorem 2. The Clique-Matching problem can be solved in O(mn 4 ) time on bipartite permutation graphs.

Proof. Let G be a bipartite permutation graph and let V 1 , V 2 be a bipartition of the vertex set. We assume without loss of generality that G has no isolated vertices. Let

n 1 = |V 1 | and n 2 = |V 2 |.
We present a dynamic programming algorithm for the problem. For simplicity, the algorithm we describe only finds the size of a maximum clique-matching M in G, but the algorithm can be modified to find a corresponding clique-matching as well.

Our algorithm starts by constructing an ordering σ 2 of V 2 that has the adjacency and enclosure properties, which can be done in linear time due to Lemma 6. From now on, we denote the vertices of V 2 by their respective rank in σ 2 , that is

V 2 = {1, . . . , n 2 }. Observe that for every vertex u ∈ V 1 , N G (u) forms an interval of σ 2 . The rightmost (resp. leftmost) neighbor of u in σ 2 is the vertex of N G (u) which is the largest (resp. smallest) in σ 2 .
Let uv ∈ E(G) with u ∈ V 1 and v ∈ V 2 be an edge in G such that uv belongs to some maximum clique-matching in G and there is no v ∈ V 2 with v < v such that v is saturated by a maximum clique-matching in G. Our algorithm guesses the edge uv by trying all different edges of G. For each guess of uv, it does as follows.

By the definition of uv, we can safely delete all vertices v ∈ V 2 with v < v. To simplify notation, we assume without loss of generality that v = 1, so uv = u1. Denote by r the rightmost neighbor of u. Then, by the adjacency property of σ 2 , we have that N G (u) = [1, r].

The algorithm now performs the following preprocessing procedure.

• Find the vertices v 1 , . . . , v l ∈ V 1 \ {u} (decreasingly ordered with respect to their rightmost neighbor) such that [1, r] ⊆ N G (v i ). By consecutively checking the intervals N G (v 1 ), . . . , N G (v l ) and selecting the rightmost available (i.e., not selected before) vertex in the considered interval, find the maximum set S = {j 1 , . . . , j h } of integers such that j 1 > . . . > j h > r and

j i ∈ N G (v i ) for i ∈ {1, . . . , h}. Delete v 1 , . . . , v h from G.
• Find the vertices x 1 , . . . , x s ∈ V 1 \ {u} (decreasingly ordered with respect to their rightmost neighbor) such that [1, 2] ⊆ N G (x i ).

• Find the vertices y 1 , . . . , y t ∈ V 1 (increasingly ordered with respect to their leftmost neighbor) such that 1 / ∈ N G (y i ) and r ∈ N G (y i ).

• Delete the vertices r + 1, . . . , n 2 from V 2 .

The structure of the neighborhoods of u, x 1 , . . . , x s and y 1 , . . . , y t after this preprocessing procedure is shown in Fig 1.

N G (x s ) N G (y t ) 1 r N G (y 1 ) N G (u) N G (x 1 )
Figure 1: Structure of the neighborhoods of u, x 1 , . . . , x s and y 1 , . . . , y t after the preprocessing procedure.

We prove that the preprocessing procedure is safe in the following claim.

Claim 1. Let M be a clique-matching of maximum size in G such that u1 ∈ M . Then there is a clique-matching M of maximum size such that u1 ∈ M and i) ∈ N G (v). By the enclosure property applied to u and v, we have that r ∈ N G (v) and v ∈ Y . Finally, because uj ∈ E(G), j ∈ N G (u) and, therefore, j ≤ r.

v 1 j 1 , . . . , v h j h ∈ M , ii) for any vj ∈ M such that vj = u1 and v / ∈ {v 1 , . . . v h }, it holds that v ∈ {x 1 , . . . , x s } ∪ {y 1 , . . . , y t } and j ∈ [2, r]. Proof of Claim 1. Let X = {x ∈ V 1 | [1, 2] ⊆ N G (x)} and let Y = {y ∈ V 1 | 1 / ∈ N G (y), r ∈ N G (
Let p = max{j | j ∈ N G (v), v ∈ X, p > r} and v ∈ X such that p ∈ N G (v). Notice that p ≥ j for any xj ∈ M . We prove that there is a clique-matching M of maximum size such that u1 ∈ M and vp ∈ M .

If vp ∈ M , then the statement trivially holds. Let vp / ∈ M . Assume that xp / ∈ M for any x ∈ V 1 , i.e., assume p is not saturated. If vj ∈ M for some j ∈ V 2 , then we construct M by replacing vj by vp in M . If vj / ∈ M for any j ∈ V 2 , that is, if v is not saturated, then we construct M by adding vp to M . For any xj ∈ M , 1 ≤ j ≤ p and, therefore, j ∈ N G (v). Hence, vj ∈ E(G) and M is a clique-matching of maximum size. Suppose now that xp ∈ M for some We apply this statement inductively to obtain a clique-matching M of maximum size such that u1 ∈ M and v 1 j 1 , . . . , v h j h ∈ M . Assume that we have a maximum clique-matching M size such that u1 ∈ M and v 1 j 1 , . . . , v i j i ∈ M . We delete v 1 , . . . , v i and j 1 , . . . , j i from the graph. Then we find p = max{j | j ∈ N G (v), v ∈ X, p > r}. If such p does not exist, we stop. Otherwise, we set j i+1 = p and find v i+1 ∈ X that is adjacent to j i+1 and find a matching that contains v i+1 j i+1 .

x ∈ V 1 . Notice that x ∈ X and [1, p] ⊆ N G (x). If vj ∈ M for some j ∈ V 2 ,
To show ii), we observe that {x 1 , . . . , x s } = X\{v 1 , . . . , v h } and {y 1 , . . . ,

y t } = Y . If vj ∈ M such that v /
∈ {v 1 , . . . v h } and j > r, then x ∈ X. But then at least one additional element should be included in the set S constructed in the preprocessing procedure, contradicting its maximality. Hence, j ∈ [2, r]. This completes the proof of Claim 1.

In the next stage of the algorithm we apply dynamic programming. For every i ∈ {0, . . . , s}, j ∈ {0, . . . , t} and non-negative integer , let c(i, j, ) denote the size of a maximum clique-matching M such that a) u1 ∈ M , b) for any vp ∈ M such that vp = u1, it holds that v ∈ {x 1 , . . . , x i } ∪ {y 1 , . . . , y j }, and c) there are at most vertices in [a i,j , b i,j ] = ( i p=1 N G (x p )) ∩ ( j q=1 N G (y q )) saturated by M .

Recall that the vertices of X and Y are ordered with respect to their rightmost and leftmost neighbors, respectively. Hence, for any 1 ≤ p < q ≤ i, we have 1 ∈ N G (x q ) ⊆ N G (x p ) ⊆ [1, r], and for any 1 ≤ p < q ≤ j, we have 1

/ ∈ N G (y q ) ⊆ N G (y p ) ⊆ [2, r]. In particular, [a i,j , b i,j ] = N G (x i )∩N G (y j ) for i, j > 0.
In other words, if [a i,j , b i,j ] = ∅, then a i,j is the left end-point of the interval N G (y j ) and b i,j is the right end-point of the interval N G (x j ). Observe that it can happen that [a i,j , b i,j ] = ∅. Observe also that c(i, j,

) = c(i, j, b i,j -a i,j + 1) if [a i,j , b i,j ] = ∅ and > b i,j -a i,j + 1. Hence, it is sufficient to compute c(i, j, ) for ≤ b i,j -a i,j + 1 ≤ n 2 .
Because all the vertices in [a i,j , b i,j ] have the same neighbors in {x 1 , . . . , x i } ∪ {y 1 , . . . , y j }, we can make the following observation. Claim 2. Let M be a clique-matching of maximum size such that M satisfies a)-c) and M has exactly f saturated vertices in [a i,j , b i,j ], and let W ⊆ [a i,j , b i,j ] be a set of size f . Then there is a clique-matching M of maximum size that satisfies a)-c) such that W is the set of vertices of [a i,j , b i,j ] saturated by M .

If i = j = 0, then we set c(i, j, ) = 1 taking into account the matching with the unique edge u1. For other values of i, j, c(i, j, ) is computed as follows. To simplify notation, we assume that x 0 = y 0 = u.

Computation of c(i, j, ) for i > 0, j = 0. Because 1 ∈ N G (x q ) ⊆ N G (x p ) ⊆ [1, r] for every 1 ≤ p < q ≤ i, any matching with edges incident to x 1 , . . . , x i is a clique-matching. This observation also implies that a maximum matching can be obtained in greedy way. Notice that [a i,0 , b i,0 ] = N G (x i ). By consecutively checking the intervals N G (x 1 ), . . . , N G (x i ) and selecting the rightmost available (i.e., not selected before) vertex in the considered interval, we find the maximum set {p 1 , . . . , p q } of integers such that t ≥ p 1 > . . . > p q > 1, p f ∈ N G (x f ) for f ∈ {1, . . . , q}, and |{p 1 , . . . , p q } ∩ [a i,0 , b i,0 ]| ≤ -1. Taking into account the edge u1, we observe that M = {u1, x 1 p 1 , . . . , x q p q } is a required matching, and we have that c(i, j, ) = q + 1.

Computation of c(i, j, ) for i = 0, j > 0. Now we have that r ∈ N G (y q ) ⊆ N G (y p ) ⊆ [2, r] for every 1 ≤ p < q ≤ j. Hence, any matching with edges incident to y 1 , . . . , y j is a clique-matching and a maximum matching can be obtained in greedy way. Notice that [a 0,j , b 0,j ] = N G (y j ). By consecutively checking the intervals N G (y 1 ), . . . , N G (y j ) and selecting the leftmost available (i.e., not selected before) vertex in the considered interval, we find the maximum set {p 1 , . . . , p q } of integers such that 1 < p 1 < . . . < p q ≤ r, p f ∈ N G (y f ) for f ∈ {1, . . . , q}, and |{p 1 , . . . , p q } ∩ [a 0,j , b 0,j ]| ≤ . It is straightforward to see that M = {u1, y 1 p 1 , . . . , y q p q } is a required matching, and we have that c(i, j, ) = q + 1.

Computation of c(i, j, ) for i > 0, j > 0. We compute c(i, j, ) using the tables of already computed values c(i -1, j , ) for j ≤ j. We find the size of a maximum clique-matching M by considering all possible choices for the vertex x i and then take the maximum among the obtained values. We distinguish three cases. Recall that [a i,j , b i,j ] = N G (x i ) ∩ N G (y j ).

Case 1. The vertex x i is not saturated by M . We have that [a

i-1,j , b i-1,j ] = N G (x i-1 ) ∩ N G (y j ) ⊆ [a i,j , b i,j ] and |[a i,j , b i,j ] \ [a i-1,j , b i-1,j ]| = b i-1,j -b i,j .
By Claim 2 implies that for any maximum clique-matching M that satisfies a)-c) and has no edge incident to x i , it holds that a clique-matching M of maximum size that satisfies a)-b), has no edge incident to x i , and has at most = + b i-1,j -b i,j saturated vertices in [a i-1,j , b i-1,j ] has the same size as M . Hence c(i, j, ) = c(i -1, j, ). Now we consider the cases when x i is saturated by M . Denote by p ∈ N G (x i ) the vertex such that x i p ∈ M . Case 2. Vertex p ∈ [a i,j , b i,j ] (see Fig. 2). Observe that p is adjacent to every vertex in {x 1 , . . . , x i-1 } ∪ {y 1 , . . . , y j }. Hence, for any edge vq such that v ∈ Case 3

N G (y j ) N G (y 1 ) 1 r N G (u) N G (x 1 ) N G (x i ) a i,j = a i-1,j b i,j b i-1,j p 1 r N G (u) N G (x 1 ) N G (x i ) b i,j b i-1,j
Case 2

a i,j p N G (y 1 ) N G (y j ) N G (y j ) a i-1,j
Figure 2: Structure of the neighborhoods of u, x 1 , . . . , x i and y 1 , . . . , y j in Cases 2 and 3.

{u} ∪ {x 1 , . . . , x i-1 } ∪ {y 1 , . . . , y j } and q = p, x i p and vq have adjacent endvertices, i.e., this choice of p does not influence the selection of other edges of M except that we can have at most -

1 other saturated vertices in [a i,j , b i,j ]. We have that [a i-1,j , b i-1,j ] = N G (x i-1 ) ∩ N G (y j ) ⊆ [a i,j , b i,j ] and |[a i,j , b i,j ] \ [a i-1,j , b i-1,j ]| = b i-1,j -b i,j
. By Claim 2, we obtain that for any maximum clique-matching M that satisfies a)-c) and x i p ∈ M , a clique-matching M of maximum size that satisfies a)-b), has no edge incident to x i and has at most

= + b i-1,j -b i,j -1 saturated vertices in [a i-1,j , b i-1,j
] has the same size as M . Hence c(i, j, ) = c(i -1, j, ).

Case 3. Vertex p /

∈ [a i,j , b i,j ], i.e., p < a i,j (see Fig. 2). Let j = max{f | p ∈ N G (y f ), 0 ≤ f ≤ j}. As p < a i,j , j < j.

Let f ∈ {j + 1, . . . , j}, g ∈ N G (y f ) and g > b i,j . Recall that b i,j is the right end-point of N G (x i ). Hence, x i g / ∈ E(G). Because f > j , x f p / ∈ E(G). We conclude that such edges cannot be in M . Similarly, let f ∈ {j + 1, . . . , j}, g ∈ N G (y f ) and g ≤ b i,j . Then for any v ∈ {x 1 , . . . , x i } ∪ {y 1 , . . . , y j }, it holds that vg ∈ E(G). Also if j + 1 ≤ f < f ≤ j, then for any g ∈ N G (x f ), x f g ∈ E(G). We have that it is safe to include in a clique-matching edges x f q for f ∈ {j +1, . . . , j}, g ∈ N G (y f ) and g ≤ b i,j . We select such edges in a greedy way. By consecutively checking the intervals N G (y j +1 ), . . . , N G (y j ) and selecting the leftmost available (i.e., not selected before) vertex in the considered interval, we find the maximum set {g 1 , . . . , g q } of integers such that p < g 1 < . . . < g q ≤ b i,j ,

g f ∈ N G (y f +j ) for f ∈ {1, . . . , q} and |{g 1 , . . . , g q } ∩ [a i,j , b i,j ]| ≤ . Claim 3.
Let M be a clique-matching of maximum size that satisfies a)-c) and x i p ∈ M . Then there is a clique-matching M of maximum size that satisfies a)-c) and x i p ∈ M such that y j +1 g 1 , . . . , y j +q g q ∈ M and for any vf ∈ M , it holds that v ∈ {y j +1 , . . . , y j +q } ∪ {x 1 , . . . , x i } ∪ {y 1 , . . . , y j }.

Proof of Claim 3. We first show inductively that for every f ∈ {1, . . . , q}, there is a clique-matching M of maximum size that satisfies a)-c) and x i p ∈ M such that y j +1 g 1 , . . . , y j +f g f ∈ M . Assume that y j +1 g 1 , . . . , y j +f -1 g f -1 ∈ M . If y j +f g f ∈ M then the statement trivially holds. Let y j +f g f / ∈ M . Suppose that g f is not saturated by M . If y j +f h for some j ∈ N G (y j +f ), then we construct M by replacing y j +f h by y j +f g f in M . If y j +f is not saturated, then we construct M by adding y j +f g f to M . We already proved that it is safe to include y j +f g f in a clique-matching, i.e., the obtained matching M is a cliquematching. Suppose now that vg f ∈ M for some v ∈ {x 1 , . . . , x i } ∪ {y 1 , . . . , y j }. Notice that v / ∈ {y j +1 , . . . , y j +f -1 } because g 1 < . . . < g f -1 < g f . Suppose that y j +f h ∈ M for some h ∈ N G (y j +f ). Then h ≤ b i,j . By the selection of g 1 , . . . , g f -1 , it holds that g f < h. It follows that h is adjacent to v. We construct M by replacing vg f , y j +f h by y j +f g f , vh in M . If y j +f is not saturated, then we construct M by replacing vg f by y j +f g f in M . We again obtain a cliquematching.

We get a clique-matching M of maximum size that satisfies a)-c) and x i p ∈ M such that y j +1 g 1 , . . . , y j +q g q ∈ M . It remains to show that for any vf ∈ M , it holds that v ∈ {y j +1 , . . . , y j +q }∪{x 1 , . . . , x i }∪{y 1 , . . . , y j }, i.e., y j +q+1 , . . . , y j are not saturated. To see this, it is sufficient to observe that otherwise our greedy procedure would have added one more element to {g 1 , . . . , g q }, contradicting the maximality of this set. This completes the proof of Claim 3.

Observe that the total number of saturated vertices in [a i-1,j , b i-1,j ] should be at most (a i,j -a i-1,j ) + (b i-1,j -b i,j ) + . Using Claims 2 and 3 and taking into account that x i p ∈ M , we obtain that c(i, j, ) = c(i -1, j , ) for = (a i,j -a i-1,j ) + (b i-1,j -b i,j ) + -(q + 1).

By our dynamic programming algorithm we eventually compute c(s, t, ) for = 0 if [a i,j , b i,j ] = ∅ or = b i,j -a i,j + 1 if [a i,j , b i,j ] = ∅. Then c(s, t, ) is the size of a maximum clique-matching M such that a) u1 ∈ M , b) for any yp ∈ M such that vp = u1, it holds that v ∈ {x 1 , . . . , x i } ∪ {y 1 , . . . , y j }.

By Claim 1, the size of a maximum clique-matching M in G such that u1 ∈ M is c(s, t, ) + |S|, where S is the set of vertices constructed during the preprocessing procedure. Recall that the algorithm tries all possible choices for the edge uv, implying that our algorithm indeed computes the size of a maximum cliquematching in G.

It remains to evaluate the running time to complete the proof. Constructing the ordering σ 2 of V 2 can be done in O(n + m) time by Lemma 6. The algorithm considers m choices for the edge uv. For each of these choices, the preprocessing procedure can be performed in O(n) time given the orderings of V 1 and V 2 (notice that Lemma 6 is symmetric with respect to V 1 , V 2 , so we can obtain an ordering of V 1 with the adjacency and enclosure properties, too). Each step of the dynamic programming can be done in O(n 2 ) time using the orderings of V 1 , V 2 . Observe that in this time we can compute c(i, j, ) for all values of . Hence, the dynamic programming algorithm runs in time O(n 4 ). We conclude that the total running time is O(mn 4 ).

Combining Lemma 5 and Theorem 2 yields the following result.

Hadwiger number of co-bipartite graphs

To conclude this section, we show that the Hadwiger Number problem is NP-complete on co-bipartite graphs.

Theorem 3. The Hadwiger Number problem is NP-complete on co-bipartite graphs.

Proof. First observe that, as a result of Lemma 2 and the observation that every edge contraction reduces the number of vertices by exactly 1, an n-vertex graph G has K p as a minor if and only if G is (n -p)-contractible to a complete graph. Hence, it suffices to prove that the Clique Contraction problem is NP-complete on co-bipartite graphs. In order to do so, we give a reduction from Not-All-Equal-3-SAT (NAE-3-SAT), which is the problem of deciding, given boolean formula ϕ in 3-CNF, whether there exists a satisfying truth assignment for ϕ that does not set all the literals of any clause to true. Let ϕ be an instance of this problem, and let x 1 , . . . , x n and c 1 , . . . , c m denote the variables and clauses of ϕ, respectively.

We construct a graph G as follows. For each i ∈ {1, . . . , n}, we create two variable vertices x i and x i , as well as the edge x i x i . Let X = {x 1 , x 1 , . . . , x n , x n }. For each clause c j , we create 4n -3 clause vertices c 1 j , . . . , c 4n-3 j each of which is made adjacent to x i (respectively x i ) if variable x i appears positively (respectively negatively) in clause c j . For each i ∈ {1, . . . , n}, we create 4n -3 dummy vertices that are made adjacent to both x i and x i but not adjacent to x j and x j for every j = i. Finally, we add edges to make X into a clique and to make V (G) \ X into a clique. This completes the construction of G.

Let k = 2n -2 and

N = |V (G) \ X| = (4n -3)(n + m).
Observe that G is a co-bipartite graph on 2n + N vertices. We claim that G is k-contractible to a complete graph if and only if ϕ is a yes-instance of NAE-3-SAT. Note that by the definition of k and N , graph G is k-contractible to a complete graph if and only if K N +2 is a contraction of G.

First suppose there exists a satisfying truth assignment t for ϕ that sets at least one literal to false in each clause. Let W 0 and W 1 denote the literals that t sets to false and true, respectively. Let G denote the graph obtained from G by contracting W i into a single vertex w i , for i ∈ {0, 1}. We claim that G is isomorphic to K N +2 . Observe that all the vertices of V (G) \ X form a clique of size N in G, and hence also in G . Moreover, each of the dummy vertices is adjacent to both w 0 and w 1 due to the fact that |W i ∩ {x j , x j }| = 1 for every i ∈ {0, 1} and j ∈ {1, . . . , n}. Finally, each of the clause vertices is adjacent to both w 0 and w 1 , since t sets at least one literal to true and at least one literal to false in each clause.

For the reverse direction, suppose G has a K N +2 -contraction structure W. Recall that for each i ∈ {1, . . . , n}, there exist 4n -3 = 2k + 1 dummy vertices that are adjacent to both x i and x i , but to no other vertex in X. Hence Lemma 1 implies that for each i ∈ {1, . . . , n}, there is a dummy vertex d i such that {d i } is a singleton of W and N G (d i ) ∩ X = {x i , x i }. Using this, we now show that there are exactly two bags W 0 , W 1 ∈ W that are included in X.

For contradiction, first suppose that at most one bag of W does not contain a vertex from V (G) \ X. Then at least N + 1 bags must contain a vertex of V (G) \ X. This is not possible, since |V (G) \ X| = N and bags are disjoint by definition. Now suppose, again for contradiction, that there are three bags of W that do not intersect V (G) \ X. Then one of them, say W , contains neither x 1 nor x 1 . But then W is not adjacent to the singleton {d 1 }, contradicting the fact that W is a K p -contraction structure of G. We conclude that there are exactly two bags W 0 , W 1 ∈ W that do not contain any vertex from V (G) \ X.

Since each of the singletons {d 1 }, . . . , {d n } is adjacent to both W 0 and W 1 , it holds that |W i ∩ {x j , x j }| = 1 for every i ∈ {0, 1} and j ∈ {1, . . . , n}. Hence we can obtain a truth assignment t for ϕ by setting the literals in W 0 to false and the literals in W 1 to true. It remains to argue that for each clause c j , at least one literal in c j is set to true and at least one literal is set to false by t. This follows from the fact that for every j ∈ {1, . . . , m}, at least one of the 4n -3 = 2k + 1 clause vertices c 1 j , . . . , c 4n-3 j forms a small bag due to Lemma 1, and hence must be adjacent to both W 0 and W 1 . This completes the proof.

Minors of Bounded Diameter

In this section, we consider a generalization of the Hadwiger Number problem where the aim is to obtain a minor of bounded diameter. Let s be a positive integer. An s-club is a graph that has diameter at most s. We consider the following problem:

Maximum s-Club Minor Instance: A graph G and a non-negative integer h. dominating set of G, i.e., each vertex of G is either in V (P ) or adjacent to a vertex of V (P ). A pair of vertices {u, v} is a dominating pair if any (u, v)path in G is a dominating path. Respectively, {u, v} is a diameter dominating pair if {u, v} is both a diameter pair and a dominating pair. Corneil, Olariu and Stewart [START_REF] Corneil | Asteroidal triple-free graphs[END_REF][START_REF]Linear time algorithms for dominating pairs in asteroidal triple-free graphs[END_REF] proved that every connected AT-free graph has a diameter dominating pair. Lemma 8 ([6,[START_REF]Linear time algorithms for dominating pairs in asteroidal triple-free graphs[END_REF]). Every connected AT-free graph has a diameter dominating pair, and such a pair can be found in O(n 3 ) time.

We need the following lemmas. Proof. Let S be a set of at most k edges of G such that H = G/S and let W = {W (x) | x ∈ V (H)} be the corresponding H-contraction structure. Because diam(H) ≤ s, H has a path Q = x 0 . . . x t such that u ∈ W (x 0 ), v ∈ W (x t ) and t ≤ s. By the definition of an H-contraction structure, for i ∈ {0, . . . , t}, there are y i , z i ∈ W (x i ) with the following properties: y 0 = u, z t = v, and z i-1 y i ∈ E(G) for i ∈ {1, . . . , t}, where y i = z i is possible. Each W (x i ) induces a connected subgraph of G. Moreover, the edges of S in G[W (x i )] compose a spanning subgraph, i.e., G i = (W (x i ), E(G[W (x i )]) ∩ S) is connected. Hence, for i ∈ {0, . . . , t}, there is a (y i , z i )-path P i in G[W (x i )] with E(P i ) ⊆ S. Denote by P the (u, v)-path P 0 + z 0 y 1 + P 1 + . . . + z t-1 y t + P t . Observe that t i=0 |E(P i )| ≤ |S| ≤ k and P has length at most k + t ≤ k + s. On the other hand, because dist G (u, v) = d, it holds that P has length at least d = k + s. This implies that t = s and P has length exactly k + t = d. It also implies that |S| = k and S ⊆ E(P ).

Lemma 10. Let G be a connected AT-free graph and let s ≥ 2 be an integer, and suppose that diam(G) > s. If k is the minimum number of edges that needs to be contracted in order to obtain a graph of diameter at most s from G, then

diam(G) -s ≤ k ≤ diam(G) -s + 2.
Proof. The bound diam(G) -s ≤ k is a straightforward corollary of Lemma 9. By Lemma 8, G has a diameter dominating pair {u, v}. Let P be a (u, v)-path in G. This path has length diam(G) ≥ diam(G) -s + 2. Let S be an arbitrary set of diam(G) -s + 2 edges of P . Let H = G/S and Q = P/S. Because P is a dominating path in G, Q is a dominating path in H. Since Q has length at most s -2, it immediately implies that diam(H) ≤ s. Hence, k ≤ diam(G) -s + 2.

Now we analyze the case when the minimum number of contracted edges is diam(G) -s + 1.

Lemma 14. Let G be a connected AT-free graph of diameter d, and let s be an integer such that 2 ≤ s ≤ d -2. Suppose that the minimum number of edges that needs to be contracted in order to obtain a graph of diameter at most s from G is k = d -s + 1. Then for any set S ⊆ E(G) of size k such that diam(G/S) ≤ s, there is a set S ⊆ S of size at most 2 such that diam(G/S ) ≥ d -|S | + 1.

Proof. Let {u, v} be a diameter dominating pair in G. Let S = {e 1 , . . . , e k } ⊆ E(G) be a set of edges such that diam(H) ≤ s for H = G/S. To obtain a contradiction, assume that for any S ⊆ S of size at most 2, diam(G/S ) ≤ d -|S |.

If there is an edge e i ∈ S such that e i is not an edge of any (u, v)-path of length d, then diam(G/e i ) = d, contradicting the assumption. Hence, every edge of S is an edge of some (u, v)-path of length d.

Suppose that for any two edges e i , e j ∈ S, there is a (u, v)-path of length d that contains them. We show that there is a (u, v)-path P of length d such that S ⊆ E(P ).

Let e i = a i b i and assume that dist

G (u, a i ) < dist G (u, b i ) for i ∈ {1, . . . , k}. If dist G (u, a i ) = dist G (
u, a j ) for some distinct i, j ∈ {1, . . . , k}, then any (u, v)-path that contains e i , e j has length at least d + 1. Hence, we can assume without loss of generality that dist G (u, a 1 ) < . . . < dist G (u, a k ). Let r ≤ k be the maximum integer such that there is a (u, v)-path P that contains e 1 , . . . , e r . Notice that r ≥ 2. If r = k, our claim holds. Let r < k. Then let P 1 be the (u, b r )-subpath of P and let P 2 be the (b r , v)-subpath of a (u, v)-path of length d containing e r , e r+1 . Because dist G (u, a r ) < dist G (u, a r+1 ), P 2 contains e r+1 . It remains to observe that the path P 1 + P 2 contains e 1 , . . . , e r+1 and has length d, contradicting the maximality of r.

Recall that |S| = k ≥ 3 and e 1 P . . . P e k . Let y 1 be the end-vertex of e 1 closest to u and let y 2 be the end-vertex of e 2 closest to u. Similarly, let z 1 be the end-vertex of e k closest to v and let z 2 be the end-vertex of e k-1 closest to v. Notice that y 1 ≺ P y 2 ≺ P z 2 ≺ P z 1 . Notice also that dist G (y 2 , z 2 ) ≥ k -2. We show the following claims.

Claim 1. For any z ∈ X v , dist G (z, y 1 ) = dist G (u, y 1 ), and for any z ∈ X u , dist G (z, z 1 ) = dist G (v, z 1 ).
Proof of Claim 1. We only show that for any z ∈ X v , dist G (z, y 1 ) = dist G (u, y 1 ); the second part of the claim follows by symmetry. Because P has length

d = diam(G), dist G (z, y 1 ) ≥ dist G (u, y 1 ) for z ∈ X v . Suppose that there is z ∈ X v such that dist G (z, y 1 ) > dist G (u, y 1 ). Then contracting e 1 does not decrease the diameter because dist G (z, v) = d for G = G/e 1 ; a contradiction. Claim 2. For any z ∈ Y v , dist G (z, y 1 ) ≤ dist G (u, y 1 ) or dist G (z, y 2 ) ≤ dist G (u, y 2 )- 1, and for any z ∈ Y u , dist G (z, z 1 ) ≤ dist G (v, z 1 ) or dist G (z, z 2 ) ≤ dist G (v, z 2 ) - 1.
Proof of Claim 2. By symmetry, it is sufficient to show that for any z

∈ Y v , dist G (z, y 1 ) ≤ dist G (u, y 1 ) or dist G (z, y 2 ) ≤ dist G (u, y 2 ) -1. Suppose that there is z ∈ Y v such that dist G (z, y 1 ) > dist G (u, y 1 ) and dist G (z, y 2 ) > dist G (u, y 2 ) -1. Let S = {e 1 , e 2 } and G = G/S . We have that dist G (z, v) = d -1, i.e., diam(G ) ≥ d -1 > diam(G) -2; a contradiction.
Observe that there exist four vertices y 1 , y 2 , z 1 , z 2 ∈ V (P ) such that y 1 ≺ P y 2 ≺ p z 2 ≺ P z 1 , y 1 P y 1 , y 2 P y 2 , z 1 P z 1 , z 2 P z 2 , and dist P (y 1 , z 1 ) = k -1. Moreover, because dist G (y 2 , z 2 ) ≥ k -2, we can select y 1 = u and z 1 = v. Let Q = x 0 . . . x k-1 be the (y 1 , z 1 )-subpath of P . Claims 1 and 2 together with Lemma 11 immediately imply that Q is an (u, v)-satisfying path of length k -1 = d -s. Moreover, u = x 0 and v = x k-1 . By Lemma 13, contracting k -1 edges in Q yields a graph of diameter at most s. But this contradicts the condition that the minimum number of edges that needs to be contracted in order to obtain a graph of diameter at most s from G is k = d -s + 1.

It remains to consider the case when there are two distinct edges e i , e j ∈ S such that any (u, v)-path of length d in G does not contain e i or e j . Let S = {e i , e j } and observe that diam(G/S ) ≥ d -1. This contradicts the assumption that diam(G/S ) ≤ d -|S |. Now we are ready to prove the main result of the section. Theorem 4. For any s ≥ 2, the s-Club Contraction problem can be solved in O(m 4 n 3 ) time on AT-free graphs. This result holds even if s is given as a part of the input.

Proof. Let (G, k) be an instance of s-Club Contraction. If G is disconnected, then G cannot be contracted to a graph of finite diameter. Notice that we can compute d = diam(G) in time O(n 3 ). If d ≤ s, the problem is trivial. From now we assume that G is connected and d > s. By Lemma 10, if k < d -s, then we have a no-instance of the problem, and if k ≥ d -s + 2, then we have a yes-instance. Hence, we can assume that d -s ≤ k ≤ d -s + 1.

Suppose that k = d -s. If k ≤ 2, we solve the problem by brute force in time O(m 2 n 3 ) by checking all possible choices of k edges. Let k ≥ 3. Using Lemma 8, we find a diameter dominating pair {u, v}. By considering all possible choices for the edges x 0 x 1 and x k-1 x k , we check for the existence of (u, v)-satisfying paths Q = x 0 . . . x k in time O(m 2 (n + m)). If such a path does not exist, then we have a no-answer due to Lemma 12. If there is a (u, v)-satisfying path Q = x 0 . . . x k with u = x 0 and v = x k , then by Lemma 13, by contracting the edges of Q we obtain a graph of diameter at most s. If we have only a (u, v)-satisfying path Q = x 0 . . . x k with u = x 0 or v = x k , then we apply Lemma 12. If u = x 0 , then we check whether x i is the unique vertex at distance i from u in G for i ∈ {0, . . . , k -2}. If this is not the case, then Lemma 12 guarantees that we have a no-answer. Otherwise, we contract the edges x i-1 x i ∈ S for i ∈ {1, . . . , k -2}. We then try all possible choices for two remaining edges and check whether we obtain a graph of diameter at most s. We use the symmetrical arguments if v = x k . Observe that the entire procedure can be performed in O(m 2 n 3 ) time.

Assume now that k = d -s + 1. First, we solve the problem for the instance (G, k -1) in O(m 2 n 3 ) time using the above procedure. Clearly, if we have a yes-instance, (G, k) is a yes-instance as well. Suppose that it is not sufficient to contract k -1 edges to obtain a graph of diameter at most s. Then we apply Lemma 14 and check, in O(m 2 ) time, all sets of edges S of size at most 2. For each set, we first check in time O(n 2 ) whether diam(G/S ) = d -|S | + 1. If so, then we solve the problem for the instance (G , k ) where G = G/S and k = k -|S |. Because k = diam(G ) -s, this can be done in O(m 2 n 3 ) time as described earlier. If we have a yes-answer for one of the instances, then we return a yes-answer. Otherwise, we have a no-answer.

It remains to observe that the total running time is O(m 4 n 3 ).

s-Club Contraction for chordal graphs

We now turn our attention to chordal graphs. Proof. First, we show hardness for 2-Club Contraction on split graphs. We reduce from the Hitting Set problem, which takes as input a finite set U , a collection S of subsets of U , and an integer k, and asks whether there exists a subset U ⊆ U of size at most k such that U contains at least one element from each subset in S; such a subset U is called a hitting set of size at most k. This problem is well-known to be NP-complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] as well as W[2]-hard when parameterized by k [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF].

Given an instance (U, S, k) of the Hitting Set problem with U = {u 1 , . . . , u n } and S = {S 1 , . . . , S m }, we create a split graph G as follows. We start by creating a vertex u i for each u i ∈ U , and we make all these vertices into a clique that we denote by U . For every S j ∈ S, we create 2k + 1 vertices S 1 j , . . . , S 2k+1 j that are made adjacent to vertex u i if and only if u i ∈ S j , for each i ∈ {1, . . . , n}. We then add a vertex x that is made adjacent to every vertex in U , as well as 2k + 1 vertices y 1 , . . . , y k+1 that are made adjacent to x only. This completes the construction of G.

Note that the vertex set of G can be partitioned into a clique U ∪ {x} and an independent set V (G) \ (U ∪ {x}), so G is a split graph. Also observe that the diameter of G is 3. Hence, in order to finish the proof, it suffices to show that G is k-contractible to a graph of diameter at most 2 if and only if (U, S, k) is a yes-instance of Hitting Set.

First suppose there exists a set U ⊆ U with |U | ≤ k such that U ∩ S j = ∅ for every j ∈ {1, . . . , m}. Consider the corresponding |U | vertices in G, contract the edges that join the vertices of U and x, and denote by w the obtained vertex. Let H denote the resulting graph. The fact that U is a hitting set implies that in H, vertex S p j is adjacent to w for every j ∈ {1, . . . , n} and p ∈ {1, . . . , 2k + 1}. This means that w is a universal vertex in implying that H has diameter at most 2.

For the reverse direction, suppose there exists a graph H of diameter at most 2 such that G is k-contractible to H. Let W be an H-contraction structure of G. Due to Lemma 1, we know that for each j ∈ {1, . . . , m}, one of the vertices S 1 j , . . . , S 2k+1 j forms a singleton, and the same holds for one of the vertices y 1 , . . . , y 2k+1 . Without loss of generality, assume that each of the vertices S 1 1 , S 1 2 . . . , S 1 m , y 1 forms a singleton. In particular, this means that every edge incident with these vertices is a witness edge, that is, an edge whose endpoints belong to two different bags. Consequently, there must be a bag W ∈ W that is adjacent to each of the vertices S 1 1 , S 1 2 . . . , S 1 m , y 1 . Due to Lemma 1, this bag W contains at most k + 1 vertices. It is clear that x ∈ W , as x is the unique neighbor of y 1 in H. Let U = W \ {x}. Since none of the vertices S 1 1 , S 1 2 . . . , S 1 m is adjacent to x, each of them is adjacent to at least one vertex in U . We conclude that U is a hitting set of size |W | -1 ≤ k.

To show that 3-Club Contraction is hard, we modify the above construction as follows. Instead of adding y 1 , . . . , y 2k+1 adjacent to x, we crate 2k + 1 vertices z 1 , . . . , z 2k+1 and make the set {z 1 , . . . , z 2k+1 , x} into a clique. Now we construct y 1 , . . . , y 2k+1 and make y i adjacent to z i for i ∈ {1, . . . , 2k + 1}. It is easy to see that the obtained graph G is chordal, and by the same arguments as above, we have that G is k-contractible to a graph of diameter at most 3 if and only if (U, S, k) is a yes-instance of Hitting Set.

Finally, let s ≥ 4. Consider a graph G and denote by G the graph obtained from G by adding k + 1 pendant vertices adjacent to v for each vertex v of G. It is straightforward to observe that G is k-contractible to a graph of diameter at most s if and only if G is k-contractible to a graph of diameter at most s -2. Clearly, if G is chordal, then G is chordal as well. As we already proved that s-Club Contraction is NP-complete as well as W[2]-hard when parameterized by k for chordal graphs for s ∈ {2, 3}, this observation immediately implies that s-Club Contraction is NP-complete and W[2]-hard for chordal graphs for every fixed s ≥ 2.

Concluding Remarks

In Section 3, we showed that the Hadwiger Number problem can be solved in polynomial time on cographs and on bipartite permutation graphs, respectively. A natural question is how far the results in those two sections can be extended to larger graph classes. An easy reduction from the Hadwiger Number problem on general graphs, involving subdividing every edge of the input graph exactly once, implies that the problem is NP-complete on bipartite graphs. Since bipartite permutation graphs form exactly the intersection of bipartite graphs and permutation graphs, and the class of permutation graphs properly contains the class of cographs, our results naturally raise the question whether the Hadwiger Number problem can be solved in polynomial time on permutation graphs. We leave this as an open question. We point out that the problem is NP-complete on co-comparability graphs, a well-known superclass of permutation graphs, due to Theorem 3 and the fact that co-bipartite graphs form a subclass of co-comparability graphs.

In Section 4, we proved that s-Club Contraction is polynomial-time solvable on AT-free graphs for s ≥ 2. An interesting direction for further research is to identify other non-trivial graph classes for which the s-Club Contraction problem is polynomial-time solvable (or fixed-parameter tractable when parameterized by k) for all values of s ≥ 2.

Theorem 1 .

 1 The Hadwiger Number problem can be solved in O(n 3 ) time on cographs.

  and because the bags of W (1) 2

  Instance: A graph G and a positive integer k. Question: Is there a clique-matching of size at least k in G? Lemma 5. If the Clique-Matching problem can be solved in f (n, m) time on chordal bipartite graphs, then the Hadwiger Number problem can be solved in O((n + m) • f (n, m)) time on this graph class.

  y)}. By the adjacency and enclosure property of σ 2 , X ∩ Y = ∅. We show that for any vj ∈ M such that vj = u1, v ∈ X ∪ Y , and if v ∈ Y , then j ≤ r. Because u1 ∈ M , j ≥ 2 and v1 ∈ E(G) or uj ∈ E(G). If v1 ∈ E(G), then by the adjacency property, [1, 2] ⊆ N G (v) and v ∈ X. If uj ∈ E(G) and 1 ∈ N G (v), then v ∈ X as well. Suppose that uj ∈ E(G) and 1 /

  then we construct M by replacing vj , xp by xj , vp in M . If vj / ∈ M for any j ∈ V 2 , then we construct M by replacing xp by vp in M . Because [1, p] ⊆ N G (v), [1, p] ⊆ N G (x) and for any yj ∈ M , 1 ≤ j ≤ p, we have that M is a clique-matching of maximum size.

Corollary 2 .

 2 The Hadwiger Number problem can be solved in O((n + m) • mn 4 ) time on bipartite permutation graphs.

Lemma 9 .

 9 Let {u, v} be a diameter pair in a connected graph G, let s ≥ 2 be an integer, and let d = diam(G) > s. If a graph H of diameter at most s can be obtained from G by contracting at set S of at most k = d -s edges, then |S| = k and there is a (u, v)-path P of length d such that S ⊆ E(P ).

Theorem 5 .

 5 For any s ≥ 2, the s-Club Contraction problem on chordal graphs is NP-complete as well as W[2]-hard when parameterized by k. Moreover, 2-Club Contraction is NP-complete and W[2]-hard when parameterized by k even on split graphs.

* The research leading to these results has received funding from the Research Council of Norway and the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 267959. A preliminary version of this paper appeared as an extended abstract in the proceedings of WG 2014.

Question: Does G have a minor with h vertices and diameter at most s?

When s = 1, the above problem is equivalent to the Hadwiger Number problem. Recall that, due to Lemma 2, the Hadwiger Number problem can be seen as the parametric dual of the Clique Contraction problem. The following straightforward lemma, which generalizes Lemma 2, will allow us to formulate the parametric dual of the Maximum s-Club Minor problem in a similar way. Lemma 7. For every connected graph G and non-negative integers p and s, the following statements are equivalent:

• G has a graph with p vertices and diameter at most s as a contraction;

• G has a graph with p vertices and diameter at most s as an induced minor;

• G has a graph with p vertices and diameter at most s as a minor.

Lemma 7 implies that for any non-negative integer s, the parametric dual of the Maximum s-Club Minor problem can be formulated as follows:

s-Club Contraction

Instance: A graph G and a positive integer k. Question: Does there exist a graph H with diameter at most s such that G is k-contractible to H?

Observe that 1-Club Contraction is NP-complete on AT-free graphs as a result of Theorem 3. We show that when s ≥ 2, the problem becomes tractable on this graph class, even if s is given as part of the input. On chordal graphs, the situation turns out to be opposite. Recall that the Hadwiger Number problem, and hence the 1-Club Contraction problem, can be solved in linear time on chordal graphs. In contrast, we show that the s-Club Contraction problem is NP-complete on chordal graphs for every fixed s ≥ 2, and the problem remains NP-complete even when restricted to split graphs in case s = 2.

s-Club Contraction for AT-free graphs

We need some additional terminology and technical results.

For two paths P = x 1 . . . x s and Q = y 1 . . . y t such that x s = y 1 and V (P ) ∩ V (Q) = {y 1 }, P + Q is the concatenation of P and Q, i.e., the path x 1 . . . x s y 2 . . . y t . For a (u, v)-path P , we write x P y if dist P (u, x) ≤ dist P (u, y), and x ≺ P y if x P y and x = y. Respectively, for xy, x y ∈ E(P ), xy P x y if x, y P x , y . Notice that we always assume that the first vertex u of P is specified whenever we use this notation.

Let G be a graph. For u, v ∈ V (G), we say that {u, v} is a diameter pair

Let us point out that the bounds in Lemma 10 are tight; if G is a path, then it is sufficient to contract diam(G) -s edges to obtain a graph of diameter at most s. If G is a graph shown in Fig. 3 for r ≥ 2, then diam(G) = 2r and it is necessary to contract 2r -s + 2 edges to obtain a graph of diameter 2 ≤ s ≤ r. Let G be a connected graph of diameter d. For a diameter pair {u, v}, let

We need the following straightforward observation.

Lemma 11. Let {u, v} be a diameter pair in a connected graph G, and let P be a (u, v)-path of length d = diam(G). If for two vertices w 1 , w 2 ∈ V (P ) such that w 1 ≺ P w 2 , it holds that i) dist G (z, w 1 ) = dist G (u, w 1 ) for any z ∈ X v , and

then for any two vertices w 1 , w 2 ∈ V (P ) such that w 1 ≺ P w 2 , w 1 ≺ P w 1 , and

Now we need the structural results given in the following three lemmas.

Lemma 11 immediately imply that conditions ii) and iii) of the definition of a (u, v)-satisfying path are fulfilled.

To show the second part of the statement of the lemma, observe that if dist P (u, z 2 ) ≥ k and dist P (v, y 2 ) ≥ k, then y 1 , y 2 , z 1 , z 2 can always be chosen in such a way that u = y 1 and v = z 1 . Hence, if for any (u, v)-satisfying

Therefore, i) follows. By the definition of z 2 , x i-1 x i ∈ S for i ∈ {1, . . . , k -2} and ii) holds.

Lemma 13. Let {u, v} be a diameter dominating pair in a connected AT-free graph G of diameter d, and let s be an integer such that

Denote by w the vertex of H obtained from x 0 , . . . , x k . By the definition, Q is a subpath of a (u, v)-path P of length d. Because {u, v} is a dominating pair, P is a dominating path in G and P = P/E(Q) is a dominating path in H. Let P 1 be the (u, w)-subpath of P and let P 2 be the (w, v)-subpath of P . Denote by s 1 the length of P 1 and denote by s 2 the length of P 2 . Clearly, s 1 , s 2 ≥ 1 and s 1 + s 2 = s. To show that diam(H) ≤ s, we have to prove that for any two vertices y, z ∈ V (H), dist H (y, z) ≤ s.

Suppose that y is a vertex of a P 1 or is adjacent to a vertex of P 1 , and z is a vertex of a P 2 or is adjacent to a vertex of P 2 . If y = w or y is adjacent to w in H, then dist H (y, w) ≤ 1 ≤ s 1 . Suppose that y = w and is not adjacent to

then y is not adjacent to u. Then y is adjacent to some other vertex of P 1 or is a vertex of P 1 and, therefore, dist H (y, w) ≤ s 1 . We have that dist H (y, w) ≤ s 1 in all cases. By the same arguments, dist H (z, w) ≤ s 2 . Therefore, dist H (y, z) ≤ s 1 + s 2 = s.

Assume now that each of y, z is a vertex of P 1 or is adjacent to a vertex of P 1 but y, z = w. If y or z is adjacent to w, we observe that this vertex is at distance at most s 2 from w and apply the same arguments as above. If y, z are not adjacent to w, then we immediately obtain that dist H (y, z) ≤ dist G (y, z) ≤ s because s 1 ≤ s-1. The case when each of y, z is a vertex of a P 2 or is adjacent to a vertex of P 2 but y, z = w is symmetric. Hence, we again have that dist H (y, z) ≤ s.