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 ti.
  • The middle layer is an n-vertex independent set with vertices mi.
  • The bottom layer is an n(n+1)-vertex clique with vertices bi,j.
  • All pairs of top and middle vertices are connected by edges.
  • Middle vertex mi and bottom vertex bj,k are connected by an edge if i=j or G has an edge vivj. That is, if vi dominates vj.

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

If G has domatic number at least d, that is, if there exist d disjoint dominating sets Si, 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 Si 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 vi of G, some representative bi,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 vi . The connected subgraph containing any top vertex tk must then include a middle vertex ml such that vl dominates vi, in order to form an adjacency between the subgraphs containing tk and bi,j. Thus, for each top vertex tk, the connected subgraph that includes tk 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.

Thus, (G,d) is a positive instance of the domatic number problem if and only if (G',h) is a positive instance of the Hadwiger number problem. This reduction (together with the easy observation that the Hadwiger number problem is in NP) completes the proof of NP-completeness.

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.