13
$\begingroup$

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).

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – David Eppstein Oct 4 '13 at 18:23
  • $\begingroup$ 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? $\endgroup$ – Chandra Chekuri Oct 6 '13 at 21:27
  • 2
    $\begingroup$ 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 $\endgroup$ – David Eppstein Oct 7 '13 at 18:46
7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.