# Complexity of computing a densest minor

Consider the following problem.
Input: An undirected graph $G=(V,E)$.
Output: A graph $H$ which is a minor of $G$ with the highest edge density among all minors of $G$, i.e., with the highest ratio $|E(H)|/|V(H)|$.

Has this problem been studied? Is it solvable in polynomial time or is it NP-hard? What if we consider restricted graph classes like classes with excluded minors?

If we ask for the densest subgraph instead, the problem is solvable in polynomial time. If we add an additional parameter $k$ and ask for the densest subgraph with $k$ vertices, the problem is NP-complete (this is an easy reduction from $k$-clique).

• My paper "Densities of minor-closed graph families" (Electronic J. Combinatorics 17(1), Paper R136, 2010, combinatorics.org/Volume_17/Abstracts/v17i1r136.html) is about densest minors, but in minor-closed graph families rather than in individual graphs. You might find something relevant to your question there. – David Eppstein Oct 4 '13 at 18:23
• This seems some what related to the following question. Given a graph $G$ what is the size of the largest clique minor in $G$? Are there any results know for it? – Chandra Chekuri Oct 6 '13 at 21:27
• Largest clique minor is NP-complete. See my paper "Finding large clique minors is hard", J. Graph Algorithms and Applications 13(2):197-204, 2009, jgaa.info/accepted/2009/Eppstein2009.13.2.pdf – David Eppstein Oct 7 '13 at 18:46

If so, it would follow that, when the density is below three, it should be possible to find the densest minor in polynomial time (with a constant factor that depends on how close to three the density is). For, the graphs whose densest minor has density $\le 3-\epsilon$ have planar forbidden minors and therefore bounded treewidth.
I found a closely related problem in a paper of Bodaender et. al.. They consider a problem called contraction degeneracy, i.e., the problem to decide for a given Graph $G$ and $k\in \mathbb{N}$ whether all minors of $G$ are $k$-degenerate. Now edge density over all subgraphs of a graph and degeneracy are very similar concepts (if a graph contains a subgraph of average degree $d$ then it also contains a subgraph of minimum degree $d/2$) and I think that their proof can be modified to show that the problem of finding a densest minor is NP-complete as well.
In fact I am quite happy with this paper because degeneracy is much nicer to work with - only natural numbers may appear as degeneracy, while the average degree over subgraphs may be any rational number. Also the paper provides a very short proof for fixed-parameter tractability using the graph minor theory of Robertson and Seymour. The class of graphs with contraction degeneracy at most $k$ is closed under taking minors and hence is described by a finite set of excluded minors. For fixed $k$ we hence have an algorithm for testing containment in the class which runs in time $O(n^3)$.