7
$\begingroup$

Are there any good algebraic/algorithmic tools available to check if a given graph $H$ is a minor of $G$ from the adjacency matrix of $G$?

$\endgroup$

2 Answers 2

11
$\begingroup$

There is a general implementation in Sage. However, the algorithm runtime grows exponentially in the size of $H$. If you have a particular small $H$ in mind, there may be more efficient implementations available.

EDIT: In the comments below, the OP clarifies that the only case of interest is $H=K_5$. For this special case, the best known algorithm is due to Bruce Reed and Zhentao Li, "Optimization and Recognition for K5-minor Free Graphs in Linear Time," LATIN 2008, LNCS 4957, pp. 206–215, 2008. Reed's website also has a draft paper with fuller algorithmic details. Unfortunately, this algorithm is very complicated and I don't know if it has been implemented; I'd recommend emailing the authors to ask.

By the way, if you find yourself having to write your own code, there is an earlier and simpler (though asymptotically less efficient) algorithm due to P. J. McGuinness and A. E. Kezdy, "Sequential and parallel algorithms to find $K_5$ minor," SODA 1992, pp. 206–215.

$\endgroup$
3
  • $\begingroup$ Isn't that even more true for particular large $H$ $\endgroup$
    – Will Sawin
    Jul 12, 2012 at 1:34
  • $\begingroup$ What I meant was that for a few special choices of $H$, there are ad hoc algorithms that do better than the general construction. $\endgroup$ Jul 12, 2012 at 2:29
  • $\begingroup$ At present I am interested in only $H=K_{5}$. Would there be any algebraic/analytic tools? $\endgroup$
    – Turbo
    Jul 12, 2012 at 3:48
6
$\begingroup$

A polynomial time algorithm for this is given in

Robertson + Seymour, Graph minors. XIII. The disjoint paths problem, Journal of Combinatorial Theory, Series B, 63 (1995), pp. 65–110.

$\endgroup$
4
  • 1
    $\begingroup$ Just to be clear: this algorithm runs in polynomial time for a fixed minor, but not if you let that vary. $\endgroup$
    – Henry Cohn
    Jul 11, 2012 at 23:17
  • 2
    $\begingroup$ And the constants in the algorithm are astronomical powers of 2 $\endgroup$ Jul 11, 2012 at 23:40
  • $\begingroup$ @gordon-royle: no argument from me... Is there a reasonable description of "practical" heuristics somewhere? $\endgroup$
    – Igor Rivin
    Jul 12, 2012 at 7:09
  • $\begingroup$ In case it wasn't clear, this is the algorithm that is implemented in the Sage code that I mentioned in my answer. $\endgroup$ Jul 12, 2012 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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