# Hadwiger hardness

The *Hadwiger number* of a graph G is the maximum number of vertices in a clique minor of G, or the maximum number of disjoint connected subgraphs of G that we can find that are all mutually adjacent to each other. It will not be surprising to learn that finding the Hadwiger number (or more precisely testing whether it is large) is NP-complete.

But what is the appropriate reference to cite for this result? I looked for it recently when improving the Wikipedia article on the related Hadwiger conjecture (that Hadwiger number is greater than or equal to chromatic number), but came up short. Suggestively, a paper by Alon, Lingas, and Wahlen on approximating the Hadwiger number didn't explicitly state its NP-completeness. Could this really have been unknown?

In case anyone doesn't believe the problem is really NP-complete, here is a proof of the standard type.**Theorem:** It is NP-complete, given a graph G and a number h, to determine whether G has Hadwiger number at least h.

*Proof:*
By reduction from domatic number.

In the domatic number problem, we are given a graph G and a number d, and asked to determine whether the domatic number (that is, the maximum number of disjoint dominating sets in G) is at least d. We may assume without loss of generality that no vertex of G is adjacent to all others, for if v is such a vertex we may simplify the problem by deleting v and subtracting one from d. As we show, the instance (G,d) may be translated in polynomial time to an equivalent instance (G',h) of the Hadwiger number problem.

So, given an n-vertex graph G in which no vertex is adjacent to all others, and a number d, construct G' in three layers:

- The top layer is a d-vertex clique with vertices t
_{i}. - The middle layer is an n-vertex independent set with vertices m
_{i}. - The bottom layer is an n(n+1)-vertex clique with vertices b
_{i,j}. - All pairs of top and middle vertices are connected by edges.
- Middle vertex m
_{i}and bottom vertex b_{j,k}are connected by an edge if i=j or G has an edge v_{i}v_{j}. That is, if v_{i}dominates v_{j}.

Let h = n(n+1)+d.

If G has domatic number at least d, that is, if there exist d disjoint dominating sets S_{i}, then G' has Hadwiger number at least n(n+1)+d. For we can form a family of mutually-adjacent connected subgraphs, where each bottom vertex forms by itself one of the subgraphs and each top vertex together with a set S_{i} forms a subgraph.

Conversely, suppose that G' has Hadwiger number at least n(n+1)+d; that is, that it has this many disjoint mutually-adjacent connected subgraphs. Each of these connected subgraphs must include a top or bottom vertex, because no two middle vertices are connected directly to each other and any single middle vertex has too few outgoing edges to be adjacent to all the other subgraphs. But because the number of subgraphs is equal to the total number of top and bottom vertices, each subgraph must have exactly one top or bottom vertex, together with possibly some middle vertices. For each vertex v_{i} of G, some representative b_{i,j} of v among the bottom vertices must form a single-vertex connected subgraph, because there are only n middle vertices to be shared among the n+1 bottom representatives of v_{i} . The connected subgraph containing any top vertex t_{k} must then include a middle vertex m_{l} such that v_{l} dominates v_{i}, in order to form an adjacency between the subgraphs containing t_{k} and b_{i,j}. Thus, for each top vertex t_{k}, the connected subgraph that includes t_{k} must include a set of middle vertices that forms a dominating set of G, and these dominating sets must be disjoint as they form a partition of the middle vertices. Therefore, the sets of middle vertices connected to each top vertex form a family of d disjoint dominating sets.

**Update, July 1:** I've asked around some more, and still not found a reference for this fact. So I made one myself: arXiv:0807.0007.

### Comments:

**None**: a tangental question

**2008-06-12T23:43:25Z**

I am trying to see the difference between Hadwiger's conjecture and Hajos' conjecture mentioned in the wikipedia page you linked. Is there a trivial example of a graph G that is contactable to Kn but does not have a subdivision of Kn as a subgraph?

**11011110**: Re: a tangental question

**2008-06-12T23:53:26Z**

The graph below has a K5 minor (just contract each of the small squares) but no K5 subdivision (there is no vertex with degree four).

**None**: Re: a tangental question

**2008-06-13T00:07:02Z**

Wow. That was quick! Thank you very much.

**None**: Re: a tangental question

**2008-06-13T04:25:27Z**

What's interesting about this is that it while it does not have a K5 subdivision, it must have a K3,3 subdivision because it is not planar.