{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T11:09:39Z","timestamp":1790766579423,"version":"4.1.0"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"ANR","award":["ANR-21-CE48-0014"],"award-info":[{"award-number":["ANR-21-CE48-0014"]}]},{"name":"ANR","award":["ANR-19-CE48-0013"],"award-info":[{"award-number":["ANR-19-CE48-0013"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We recently introduced the notion of twin-width, a novel graph invariant, and showed that first-order model checking can be solved in time [Formula: see text] for [Formula: see text]-vertex graphs given with a witness that the twin-width is at most [Formula: see text], called [Formula: see text]-contraction sequence or [Formula: see text]-sequence, and formulas of size [Formula: see text] [Bonnet et\u00a0al., JACM \u201922]. The inevitable price to pay for such a general result is that [Formula: see text] is a tower of exponentials of height roughly [Formula: see text]. In this paper, we show that algorithms based on twin-width need not be impractical. We present [Formula: see text]-time algorithms for [Formula: see text]-independent set, [Formula: see text]-scattered set, [Formula: see text]-clique, and [Formula: see text]-dominating set when an [Formula: see text]-sequence of the graph is given in input. We further show how to solve the weighted version of [Formula: see text]-independent set, subgraph isomorphism, and induced subgraph isomorphism in the slightly worse running time [Formula: see text]. Up to logarithmic factors in the exponent, all these running times are optimal unless the exponential time hypothesis fails. Like our first-order model checking algorithm, these new algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence by starting at its end and rewinding it. As an example of such a reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, thereby establishing that bounded twin-width classes are [Formula: see text]-bounded. This significantly extends the [Formula: see text]-boundedness of bounded rank-width classes and does so with a very concise proof. It readily yields a constant approximation for max independent set on [Formula: see text]-free graphs of bounded twin-width and a [Formula: see text]-approximation for min coloring on bounded twin-width graphs. We further observe that a constant approximation for max independent set on bounded twin-width graphs (but arbitrarily large clique number) would actually imply a polynomial-time approximation scheme. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques such that both sides of the bicliques are on consecutive vertices in a fixed vertex ordering. This property is trivially shared with graphs of bounded average degree. Given that biclique edge-partition, we show how to solve the unweighted single-source shortest paths, and hence all-pairs shortest paths, in time [Formula: see text] and time [Formula: see text], respectively. In sharp contrast, even diameter does not admit a truly subquadratic algorithm on bounded twin-width graphs unless the strong exponential time hypothesis fails. The fourth algorithmic use of twin-width builds on the so-called versatile tree of contractions [Bonnet et\u00a0al., Comb.\u00a0Theory \u201922], a branching and more robust witness of low twin-width. We present constant-approximation algorithms for min dominating set and related problems on bounded twin-width graphs by showing that the integrality gap is constant. This is done by going down the versatile tree and stopping according to a problem-dependent criterion. At the reached node, a greedy approach yields the desired approximation.<\/jats:p>","DOI":"10.1137\/21m142188x","type":"journal-article","created":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T04:55:22Z","timestamp":1729054522000},"page":"1602-1640","source":"Crossref","is-referenced-by-count":10,"title":["Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring"],"prefix":"10.1137","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":true,"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[{"name":"Universit\u00e9 Lyon, CNRS, ENS de Lyon, Universit\u00e9 Claude Bernard Lyon 1, LIP UMR5668, Lyon 69634 France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Colin","family":"Geniet","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw 00-927 Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6824-0516","authenticated-orcid":true,"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[{"name":"School of Computing, KAIST, Daejeon, Korea."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Lyon, CNRS, ENS de Lyon, Universit\u00e9 Claude Bernard Lyon 1, LIP UMR5668, Lyon 69634 France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R\u00e9mi","family":"Watrigant","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Lyon, CNRS, ENS de Lyon, Universit\u00e9 Claude Bernard Lyon 1, LIP UMR5668, Lyon 69634 France."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,10,16]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.12.008"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"ref3","first-page":"10","volume-title":"STACS 2023","author":"Berg\u00e9 P.","year":"2023"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"ref5","author":"Bonamy M.","year":"2020","journal-title":"Adv. Comb."},{"key":"ref6","volume":"2","author":"Bonnet \u00c9.","year":"2022","journal-title":"Comb. Theory"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-00965-5"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3486655"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-020-4423-3"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/0215051"},{"key":"ref11","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/3310228"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305948"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"ref18","unstructured":"F. Dorn, Planar subgraph isomorphism revisited, in 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Nancy, France, 2010, pp. 263\u2013274."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.12.005"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.12.004"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"ref23","author":"Evald J.","year":"2016","journal-title":"Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs"},{"key":"ref24","first-page":"2","volume-title":"Proceedings 32nd Annual Symposium of Foundations of Computer Science","author":"Feige U.","year":"1991"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.01.007"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"A. Grzesik, T. Klimosova, M. Pilipczuk, and M. Pilipczuk, Polynomial-time algorithm for maximum weight independent set on \\({P}_6\\)-free graphs, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms 2019, SIAM, Philadelphia, 2019, pp. 1257\u20131271, https:\/\/doi.org\/10.1137\/1.9781611975482.77.","DOI":"10.1137\/1.9781611975482.77"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"S. Guillemot and D. Marx, Finding small patterns in permutations in linear time, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms 2014, SIAM, Philadelphia, 2014, pp. 82\u2013101, https:\/\/doi.org\/10.1137\/1.9781611973402.7.","DOI":"10.1137\/1.9781611973402.7"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"ref36","unstructured":"S. Kratsch and F. Nelles, Efficient parameterized algorithms for computing all-pairs shortest paths, in 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2020, pp. 38:1\u201338:15, https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.38."},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"M. Pilipczuk and S. Siebertz, Polynomial bounds for centered colorings on proper minor-closed graph classes, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms 2019, SIAM, Philadelphia, 2019, pp. 1501\u20131520, https:\/\/doi.org\/10.1137\/1.9781611975482.91.","DOI":"10.1137\/1.9781611975482.91"},{"key":"ref39","first-page":"307","volume":"15","author":"Poljak S.","year":"1974","journal-title":"Comment. Math. Univ. Carolin."},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"J. M. Schmidt, Interval stabbing problems in small integer ranges, in Algorithms and Computation, 20th International Symposium (ISAAC 2009), Lecture Notes in Comput. Sci. 5878, Springer, Cham, 2009, pp. 163\u2013172.","DOI":"10.1007\/978-3-642-10631-6_18"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm038"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-018-0353-z"},{"key":"ref43","doi-asserted-by":"crossref","unstructured":"R. Yuster, Efficient algorithms on sets of permutations, dominance, and real-weighted APSP, in SODA \u201909: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, SIAM, Philadelphia, 2009, pp. 950\u2013957.","DOI":"10.1137\/1.9781611973068.103"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M142188X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:17Z","timestamp":1787337017000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M142188X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,16]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1137\/21M142188X"],"URL":"https:\/\/doi.org\/10.1137\/21m142188x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,16]]}}}