Skip to main content
http -> https (the question was bumped anyway)
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

There is a general implementation in SageSage. 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 paperdraft 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.

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.

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.

added 838 characters in body
Source Link
Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587

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.

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.

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.

Source Link
Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587

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.