Timeline for How unhelpful is graph minors theorem?
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 2, 2010 at 3:18 | history | edited | Rune | CC BY-SA 2.5 |
pointed at correction in comments
|
| Jan 2, 2010 at 3:17 | comment | added | Rune | I was unaware of this having gone on for a while. That's disappointing. Thanks for the information. | |
| Jan 1, 2010 at 21:02 | comment | added | David Eppstein | Reed has been claiming an O(n^2) algorithm for years without publishing details and has now moved up to claiming O(n log n). I think that making such claims without backing them up does serious damage to the subject since it throws into doubt anything that relies on the claims and prevents others from working on the problem and actually publishing their algorithms. | |
| Jan 1, 2010 at 20:24 | comment | added | Rune | I was indeed talking about Bruce Reed's claimed algorithm. I am also waiting to see the writeup. | |
| Jan 1, 2010 at 18:23 | comment | added | David Eppstein | As for "the polynomial is like O(n log n)": Reed has claimed something like this, I think, but until he actually publishes the full details I think we have to rely on the O(n^3) Robertson–Seymour algorithm from Graph Minors XIII, doi:10.1006/jctb.1995.1006. | |
| Jan 1, 2010 at 18:18 | comment | added | David Eppstein | @Gil: Yes, there exist linear time algorithms for bounded-genus embedding (e.g. Kawarabayashi, Mohar, and Reed, FOCS'08, doi:10.1109/FOCS.2008.53) but I don't think the forbidden minors are known for all bounded genus embeddings. | |
| Jan 1, 2010 at 11:10 | comment | added | Gil Kalai | Cant we test quickly if a graph is embeddable in a surface of genus 5 (say)? | |
| Jan 1, 2010 at 3:24 | comment | added | Ilya Nikokoshev | Yes, this is the argument one can make about 2 and 3, but I suspect there would be equally valid arguments with the contrary view. | |
| Dec 31, 2009 at 20:31 | history | answered | Rune | CC BY-SA 2.5 |