<p>I found a closely related problem in a <a href="http://jgaa.info/accepted/2006/BodlaenderWolleKoster2006.10.1.pdf">paper of Bodaender et. al.</a>. 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. </p>

<p>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)$. </p>

CC BY-SA 3.0
2013-10-24T15:10:28.903Z
2013-10-24T15:10:28.903Z
Sebastian Siebertz
<p>Ok, since there's still nothing here in the way of an answer, let me at least make a couple of simple observations:</p>

<p>For graphs of bounded treewidth it should be possible to find a densest minor (or even a minor with specified numbers of edges and vertices) by the usual sort of dynamic program on the tree decomposition, where each state of the dynamic program keeps track of the number of edges and vertices in the part of the minor living in a subtree of the decomposition, the subset of vertices in the bag of the decomposition that participate in the minor, the equivalences between vertices in this subset caused by the minor contractions in the whole graph, and a refinement of this equivalence relation caused by the contractions in the part of the minor living in the subtree.</p>

<p>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.</p>

CC BY-SA 3.0
2013-10-06T07:38:50.513Z
2013-10-06T07:38:50.513Z
David Eppstein
<p>Consider the following problem.<br>
Input: An undirected graph $G=(V,E)$.<br>
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)|$.</p>

<p>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?</p>

<p>If we ask for the densest subgraph instead, the <a href="http://epubs.siam.org/action/showAbstract?page=30&amp;volume=18&amp;issue=1&amp;journalCode=smjcat&amp;">problem is solvable in polynomial time</a>. 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). </p>

CC BY-SA 3.0
2013-10-04T18:23:21.677Z
My paper "Densities of minor-closed graph families" (Electronic J. Combinatorics 17(1), Paper R136, 2010, http://www.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
CC BY-SA 3.0
2013-10-06T21:27:15.107Z
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
CC BY-SA 3.0
2013-10-07T18:46:14.563Z
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, http://jgaa.info/accepted/2009/Eppstein2009.13.2.pdf
David Eppstein
<graph-theory><graph-algorithms><np-hardness><graph-minor>
Complexity of computing a densest minor
Sebastian Siebertz
# Complexity of computing a densest minor

(Asked by: username_0 on 2013-10-04)

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](http://epubs.siam.org/action/showAbstract?page=30&volume=18&issue=1&journalCode=smjcat&). 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).

**Tags:** graph-theory, graph-algorithms, np-hardness, graph-minor
> **Comments:**
> **username_1**: My paper "Densities of minor-closed graph families" (Electronic J. Combinatorics 17(1), Paper R136, 2010, http://www.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.  
> **username_2**: 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?  
> **username_1**: 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, http://jgaa.info/accepted/2009/Eppstein2009.13.2.pdf  

---

## 2 answers

### Answer by username_0 on 2013-10-24. Score: 7

I found a closely related problem in a [paper of Bodaender et. al.](http://jgaa.info/accepted/2006/BodlaenderWolleKoster2006.10.1.pdf). 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)$.


---

### Answer by username_1 on 2013-10-06. Score: 7

Ok, since there's still nothing here in the way of an answer, let me at least make a couple of simple observations:

For graphs of bounded treewidth it should be possible to find a densest minor (or even a minor with specified numbers of edges and vertices) by the usual sort of dynamic program on the tree decomposition, where each state of the dynamic program keeps track of the number of edges and vertices in the part of the minor living in a subtree of the decomposition, the subset of vertices in the bag of the decomposition that participate in the minor, the equivalences between vertices in this subset caused by the minor contractions in the whole graph, and a refinement of this equivalence relation caused by the contractions in the part of the minor living in the subtree.

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.


---

