1
$\begingroup$

I'm looking for any results regarding computing the number of graphs of size $n$ which have a given graph $H$ as a minor. Are there any known algorithms which are more efficient than a brute force search?

Any other results related to this question are of interest as well.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ If by brute force you mean testing for an $H$-minor for every graph on $n$ vertices, that will be astronomical in practice. Minor testing can be done in $O(n^3)$-time, but the constants from graph minors are so large that no one has really implemented the algorithm. So even a single iteration of $H$-minor testing is not really feasible. Note that there are at least $2^{\binom{n}{2}-|E(H)|}$ graphs with an $H$-subgraph (and hence also an $H$-minor) on $n$ vertices. Do you need a more accurate estimate than that? $\endgroup$
    – Tony Huynh
    Commented Feb 16, 2016 at 3:07
  • 1
    $\begingroup$ I can't imagine anything non-horrendous except for very simple $H$s. $\endgroup$
    – Brendan McKay
    Commented Feb 16, 2016 at 4:04
  • $\begingroup$ @Tony Huynh I'm primarily interested in the number of graphs with $H$ as a minor, the asymptotic result is fine, but an algorithm to compute the value would be preferred. I am looking at the question purely out of interest, so I don't really have a criteria for what constitutes an acceptable answer. $\endgroup$
    – Davis Yoshida
    Commented Feb 18, 2016 at 1:28
  • $\begingroup$ Just to suggest a slight improvement on a brute-force search, you could construct the graphs using $H$ from the bottom up. Start with $H$ and build every possible graph that has $H$ as a simple minor (the result of a single edge deletion or contraction) and at most size $n$. Then on those graphs perform the same operation of building all the graphs that have them as a simple minor. This will create a tree of graphs that terminates as the size of the graphs approaches $n$. While doing this, keep track of the size and order of the graphs created and delete duplicates up to isomorphism. $\endgroup$
    – Mike Pierce
    Commented Aug 25, 2016 at 15:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .