tag:blogger.com,1999:blog-6555947.post1909593309987089238..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Graphs excluding a fixed minorSuresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6555947.post-34453109208468245692010-02-12T10:05:53.204-07:002010-02-12T10:05:53.204-07:00Chandra: true, although I was asking because someo...Chandra: true, although I was asking because someone actually wanted an algorithm :). the RS route is hopeless.<br /><br />regarding the approximability though, see David's link above. The problem of finding a largest clique *minor* is actually easier than finding a largest clique subgraph. In his paper, he cites a paper by Alon, Lingas and Wahlen that shows a sqrt{n} approximation for this number (called the Hadwiger number)Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-21429872753150423242010-02-12T08:53:00.649-07:002010-02-12T08:53:00.649-07:00For a fixed H, there is a polynomial time algorith...For a fixed H, there is a polynomial time algorithm via Robertson-Seymour (n^3 time and dependence on |H| is terrible) that checks if G excludes H. Thus, for a fixed constant k, one can in polynomial time check whether G excludes any H-minor with |V(H)| <= k. Basically try all graphs of size <= k. Essentially the problem is fixed parameter tractable.<br /><br />On the other hand, the general problem where one wants to find the smallest H that is excluded in G is as hard as clique. More precisely, it is NP-Hard to distinguish whether a given graph has a clique of size n^{1-\eps} or less than n^{\eps}. If G has a clique of size n^{1-\eps} then it includes a minor for every graph of size n^{1-\eps}. If G has no clique of size more than n^{\eps} than clearly G excludes a clique of this size. So the problem is hard to approximate to within n^{1-\eps} for every \eps > 0.Chandrahttp://www.blogger.com/profile/00057069075567569157noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-51576808885320667332010-02-12T00:38:13.707-07:002010-02-12T00:38:13.707-07:00It's definitely NP-hard to find the smallest e...It's definitely NP-hard to find the smallest excluded minor if you measure "smallest" by number of vertices: http://arxiv.org/abs/0807.000711011110http://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-6911479255967290532010-02-12T00:04:54.994-07:002010-02-12T00:04:54.994-07:00Oooooooh, parametric complexity!? A bunch of my co...Oooooooh, parametric complexity!? A bunch of my colleagues in Jena were heavily into these things!Mikael Vejdemo-Johanssonhttp://www.blogger.com/profile/00008302080954798496noreply@blogger.com