{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:45Z","timestamp":1781031465377,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"NSF","award":["DMS-2348219"],"award-info":[{"award-number":["DMS-2348219"]}]},{"name":"NSF","award":["CCF-250510"],"award-info":[{"award-number":["CCF-250510"]}]},{"name":"AFOSR","award":["FA9550-25-1-0275"],"award-info":[{"award-number":["FA9550-25-1-0275"]}]},{"name":"NSF","award":["CCF-2505099"],"award-info":[{"award-number":["CCF-2505099"]}]},{"name":"ISF","award":["687\/2"],"award-info":[{"award-number":["687\/2"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800723","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"19-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Forbidden Subgraphs of Graphs with Low Bandwidth"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8920-4944","authenticated-orcid":false,"given":"Maria","family":"Chudnovsky","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3166-9212","authenticated-orcid":false,"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, Santa Barbara, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1671-7765","authenticated-orcid":false,"given":"Eran","family":"Nevo","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"},{"name":"Universidad de Valladolid, Valladolid, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602041"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90066-9"},{"key":"e_1_3_2_1_3_1","first-page":"274","article-title":"Quickly excluding a forest.. J. Comb. Theory","volume":"52","author":"Bienstock Daniel","year":"1991","unstructured":"Daniel Bienstock, Neil Robertson, Paul D Seymour, and Robin Thomas. 1991. Quickly excluding a forest.. J. Comb. Theory, Ser. B, 52, 2 (1991), 274\u2013283.","journal-title":"Ser. B"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_3_2_1_5_1","volume-title":"Hallett","author":"Bodlaender Hans L.","year":"1994","unstructured":"Hans L. Bodlaender, Michael R. Fellows, and Michael T. Hallett. 1994. Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy. In STOC. 449\u2013458."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-021-10030-3"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"key":"e_1_3_2_1_9_1","volume-title":"A simple linear-time algorithm for finding path-decompositions of small width. Information processing letters, 57, 4","author":"Cattell Kevin","year":"1996","unstructured":"Kevin Cattell, Michael J Dinneen, and Michael R Fellows. 1996. A simple linear-time algorithm for finding path-decompositions of small width. Information processing letters, 57, 4 (1996), 197\u2013203."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820609"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127211"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060302"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90083-6"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. 645\u2013654","author":"Chuzhoy Julia","year":"2015","unstructured":"Julia Chuzhoy. 2015. Excluded grid theorem: Improved and simplified. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. 645\u2013654."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.09.010"},{"key":"e_1_3_2_1_16_1","unstructured":"Jarmila Chv\u00e1talov\u00e1. 1982. On The Bandwidth Problem for Graphs.. Ph. D. Dissertation."},{"key":"e_1_3_2_1_17_1","volume-title":"The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation, 85, 1","author":"Courcelle Bruno","year":"1990","unstructured":"Bruno Courcelle. 1990. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation, 85, 1 (1990), 12\u201375."},{"key":"e_1_3_2_1_18_1","first-page":"40","article-title":"Exact and approximate bandwidth","volume":"411","author":"Cygan Marek","year":"2010","unstructured":"Marek Cygan and Marcin Pilipczuk. 2010. Exact and approximate bandwidth. Theoretical Computer Science, 411, 40-42 (2010), 3701\u20133713.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_1_19_1","first-page":"4","article-title":"Bandwidth and distortion revisited","volume":"160","author":"Cygan Marek","year":"2012","unstructured":"Marek Cygan and Marcin Pilipczuk. 2012. Bandwidth and distortion revisited. Discret. Appl. Math., 160, 4-5 (2012), 494\u2013504.","journal-title":"Discret. Appl. Math."},{"key":"e_1_3_2_1_20_1","article-title":"Even Faster Exact Bandwidth","volume":"8","author":"Cygan Marek","year":"2012","unstructured":"Marek Cygan and Marcin Pilipczuk. 2012. Even Faster Exact Bandwidth. ACM Trans. Algorithms, 8, 1 (2012), 8:1\u20138:14.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_2_1_21_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel. 2012. Graph Theory, 4th Edition (Graduate texts in mathematics, Vol. 173). Springer. isbn:978-3-642-14278-9","edition":"4"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200412"},{"key":"e_1_3_2_1_23_1","volume-title":"Parameterized complexity. 3","author":"Downey Rod G","unstructured":"Rod G Downey and Michael Ralph Fellows. 1999. Parameterized complexity. 3, Springer."},{"key":"e_1_3_2_1_24_1","volume-title":"Beyond the question of fixed-parameter tractability. Ph. D. Dissertation","author":"Dregi Markus Fanebust","unstructured":"Markus Fanebust Dregi. 2017. Beyond the question of fixed-parameter tractability. Ph. D. Dissertation. The University of Bergen."},{"key":"e_1_3_2_1_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"Parameterized Complexity of Bandwidth on Trees","author":"Dregi Markus Sortland","unstructured":"Markus Sortland Dregi and Daniel Lokshtanov. 2014. Parameterized Complexity of Bandwidth on Trees. Lecture Notes in Computer Science, Vol. 8572. Springer, 405\u2013416."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.006"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"John Dunagan and Santosh Vempala. 2001. On Euclidean Embeddings and Bandwidth Minimization. In RANDOM-APPROX. 229\u2013240.","DOI":"10.1007\/3-540-44666-4_26"},{"key":"e_1_3_2_1_28_1","volume-title":"Graph separation and search number","author":"Ellis John Arthur","unstructured":"John Arthur Ellis, I Hal Sudborough, and Jonathan S Turner. 1987. Graph separation and search number. University of Victoria. Department of Computer Science."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","first-page":"347","DOI":"10.4153\/CJM-1965-035-8","article-title":"On Independent Circuits Contained in a Graph","volume":"17","author":"Erd\u00f6s Paul","year":"1965","unstructured":"Paul Erd\u00f6s and Lajos P\u00f3sa. 1965. On Independent Circuits Contained in a Graph. Canadian Journal of Mathematics, 17 (1965), 347\u2013352.","journal-title":"Canadian Journal of Mathematics"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the thirtieth annual ACM symposium on Theory of computing. 90\u201399","author":"Feige Uriel","year":"1998","unstructured":"Uriel Feige. 1998. Approximating the bandwidth via volume respecting embeddings. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. 90\u201399."},{"key":"e_1_3_2_1_31_1","volume-title":"7th Scandinavian Workshop on Algorithm Theory","volume":"19","author":"Feige Uriel","year":"2000","unstructured":"Uriel Feige. 2000. Coping with the NP-Hardness of the Graph Bandwidth Problem. In Algorithm Theory - SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000, Proceedings, Magn\u00fas M. Halld\u00f3rsson (Ed.) (Lecture Notes in Computer Science, Vol. 1851). Springer, 10\u201319."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9002-0"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.3390\/a13060146"},{"key":"e_1_3_2_1_34_1","volume-title":"International Workshop on Combinatorial Algorithms. 385\u2013396","author":"F\u00fcrer Martin","year":"2016","unstructured":"Martin F\u00fcrer. 2016. Faster computation of path-width. In International Workshop on Combinatorial Algorithms. 385\u2013396."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.03.024"},{"key":"e_1_3_2_1_36_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA. isbn:0716710447"},{"key":"e_1_3_2_1_37_1","volume-title":"Liu","author":"George Alan","year":"1981","unstructured":"Alan George and Joseph W. Liu. 1981. Computer Solution of Large Sparse Positive Definite. Prentice Hall Professional Technical Reference. isbn:0131652745"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.011"},{"key":"e_1_3_2_1_39_1","unstructured":"Anupam Gupta. 2000. Improved bandwidth approximation for trees. In SODA. 788\u2013793."},{"key":"e_1_3_2_1_40_1","volume-title":"44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. 534\u2013543","author":"Gupta Anupam","year":"2003","unstructured":"Anupam Gupta, Robert Krauthgamer, and James R Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. 534\u2013543."},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 24\u201335","author":"Guruswami Venkatesan","year":"2024","unstructured":"Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. 2024. Parameterized inapproximability hypothesis under exponential time hypothesis. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 24\u201335."},{"key":"e_1_3_2_1_42_1","volume-title":"Theory of graphs and its applications","author":"Harary Frank","year":"1967","unstructured":"Frank Harary. 1967. Problem 16. Theory of graphs and its applications, Czechoslovak Academy of Science, Prague, 818 (1967)."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80059-5"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.11.001"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875596"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.6"},{"key":"e_1_3_2_1_47_1","volume-title":"50th Annual ACM Symposium on Theory of Computing. 1283\u20131296","author":"Karthik CS","year":"2018","unstructured":"CS Karthik, Bundit Laekhanukit, and Pasin Manurangsi. 2018. On the parameterized complexity of approximating dominating set. In 50th Annual ACM Symposium on Theory of Computing. 1283\u20131296."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.09.006"},{"key":"e_1_3_2_1_49_1","volume-title":"Obstruction set isolation for layout permutation problems. Ph. D. Dissertation","author":"Kinnersley Nancy Gail","unstructured":"Nancy Gail Kinnersley. 1989. Obstruction set isolation for layout permutation problems. Ph. D. Dissertation. Washington State University."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90234-M"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1137\/0403033","article-title":"Computing the bandwidth of interval graphs","volume":"3","author":"Kleitman Daniel J","year":"1990","unstructured":"Daniel J Kleitman and Rakesh V Vohra. 1990. Computing the bandwidth of interval graphs. SIAM Journal on Discrete Mathematics, 3, 3 (1990), 373\u2013375.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/1379218.1379219"},{"key":"e_1_3_2_1_53_1","volume-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 1749\u20131756","author":"Lin Bingkai","year":"2021","unstructured":"Bingkai Lin. 2021. Constant approximating k-clique is W[1]-hard. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 1749\u20131756."},{"key":"e_1_3_2_1_54_1","first-page":"008690","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Linial Nathan","year":"2002","unstructured":"Nathan Linial. 2002. Finite metric-spaces\u2014combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians (Beijing, 2002). III, Higher Education Press, 573\u2013586. isbn:7-04-008690-5"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"e_1_3_2_1_56_1","first-page":"589","article-title":"Bi-Lipschitz embeddings into low-dimensional Euclidean spaces","volume":"31","author":"Matou\u0161ek Ji\u0159\u00ed","year":"1990","unstructured":"Ji\u0159\u00ed Matou\u0161ek. 1990. Bi-Lipschitz embeddings into low-dimensional Euclidean spaces. Commentationes Mathematicae Universitatis Carolinae, 31, 3 (1990), 589\u2013600.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/0607057"},{"key":"e_1_3_2_1_58_1","volume-title":"Sparsity: graphs, structures, and algorithms","author":"Nesetril Jaroslav","unstructured":"Jaroslav Nesetril and Patrice Ossona De Mendez. 2014. Sparsity: graphs, structures, and algorithms. Springer Publishing Company, Incorporated."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280884"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.12.025"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM.","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/0601042"},{"key":"e_1_3_2_1_65_1","volume-title":"Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel","author":"Scheffler Petra","unstructured":"Petra Scheffler. 1990. A linear algorithm for the pathwidth of trees. In Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel. Springer, 613\u2013620."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.11.010"},{"key":"e_1_3_2_1_67_1","unstructured":"Jing-Ho Yan. 1997. The bandwidth problem in cographs. Tamsui Oxford Journal of Mathematical Sciences 31\u201336."}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800723","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800723","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:17Z","timestamp":1781028257000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800723"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":67,"alternative-id":["10.1145\/3798129.3800723","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800723","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}