{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:58:20Z","timestamp":1775595500008,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2017,12,17]],"date-time":"2017-12-17T00:00:00Z","timestamp":1513468800000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1016684, CCF-1319376, CCF-0844872, CCF-1318242"],"award-info":[{"award-number":["CCF-1016684, CCF-1319376, CCF-0844872, CCF-1318242"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,12,20]]},"abstract":"<jats:p>\n                    One of the key results in Robertson and Seymour\u2019s seminal work on graph minors is the grid-minor theorem (also called the\n                    <jats:italic toggle=\"yes\">excluded grid theorem<\/jats:italic>\n                    ). The theorem states that for every grid\n                    <jats:italic toggle=\"yes\">H<\/jats:italic>\n                    , every graph whose treewidth is large enough relative to |\n                    <jats:italic toggle=\"yes\">V<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">H<\/jats:italic>\n                    )| contains\n                    <jats:italic toggle=\"yes\">H<\/jats:italic>\n                    as a minor. This theorem has found many applications in graph theory and algorithms. Let\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    ) denote the largest value such that every graph of treewidth\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    contains a grid minor of size (\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    ) \u00d7\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    )). The best previous quantitative bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    )=\u03a9(\u221alog\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    \/log log\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    ). In contrast, the best known upper bound implies that\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    ) =\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\u221a\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    \/log\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    ). In this article, we obtain the first polynomial relationship between treewidth and grid minor size by showing that\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    ) = \u03a9(\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    <jats:sup>\u03b4<\/jats:sup>\n                    ) for some fixed constant \u03b4 &gt; 0, and describe a randomized algorithm, whose running time is polynomial in |\n                    <jats:italic toggle=\"yes\">V<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    )| and\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    , that with high probability finds a model of such a grid minor in\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    .\n                  <\/jats:p>","DOI":"10.1145\/2820609","type":"journal-article","created":{"date-parts":[[2016,12,19]],"date-time":"2016-12-19T12:06:31Z","timestamp":1482149191000},"page":"1-65","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Polynomial Bounds for the Grid-Minor Theorem"],"prefix":"10.1145","volume":"63","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana-Champaign, Urbana, IL"}]},{"given":"Julia","family":"Chuzhoy","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago IL"}]}],"member":"320","published-online":{"date-parts":[[2016,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.33"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488645"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722148"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627841"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060618"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/100796820"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_22"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Chandra Chekuri Guyslain Naves and F. Bruce Shepherd. 2013b. Maximum edge-disjoint paths in k-sums of graphs. arXiv:1303.4897.","DOI":"10.1007\/978-3-642-39206-1_28"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746551"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/130910464"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2893472"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00022-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9138-y"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2140-4"},{"key":"e_1_2_1_17_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel. 2012. Graph Theory (4th ed.). Graduate Texts in Mathematics, Vol. 173. Springer.","edition":"4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1862"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1568639"},{"key":"e_1_2_1_20_1","first-page":"601","article-title":"Proof of a conjecture of P","volume":"2","author":"Hajnal A.","year":"1970","unstructured":"A. Hajnal and E. Szemer\u00e9di. 1970. Proof of a conjecture of P. Erdos. Combinatorial Theory and Its Applications 2, 601--623.","journal-title":"Erdos. Combinatorial Theory and Its Applications"},{"key":"e_1_2_1_21_1","first-page":"179","article-title":"Menger-type results for three or more vertices","volume":"113","author":"Hind H. R.","year":"1996","unstructured":"H. R. Hind and O. Oellermann. 1996. Menger-type results for three or more vertices. Congressus Numerantium 113, 179--204.","journal-title":"Congressus Numerantium"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","author":"Kawarabayashi Kenichi","year":"2012","unstructured":"Kenichi Kawarabayashi and Yusuke Kobayashi. 2012. Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912). 278--289."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538903"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873631"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.09.003"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70504-1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374442"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652152"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958023"},{"key":"e_1_2_1_30_1","volume-title":"Surveys in Combinatorics","author":"Reed Bruce","unstructured":"Bruce Reed. 1997. Treewidth and tangles: A new connectivity measure and some applications. In Surveys in Combinatorics. Cambridge University Press, 87--162."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"e_1_2_1_34_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, Vol. 24. Springer."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629366"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788671"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2820609","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2820609","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2820609","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:44:22Z","timestamp":1763459062000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2820609"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,17]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,12,20]]}},"alternative-id":["10.1145\/2820609"],"URL":"https:\/\/doi.org\/10.1145\/2820609","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,17]]},"assertion":[{"value":"2014-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}