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 \( \mathsf{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 \( \mathsf{NP} \)-completeness. Could this really have been unknown?

In case anyone doesn't believe the problem is really \( \mathsf{NP} \)-complete, here is a proof of the standard type.

Theorem: It is \( \mathsf{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_i \) 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.

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 \( \mathsf{NP} \)) completes the proof of \( \mathsf{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: