{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:16Z","timestamp":1781077696140,"version":"3.54.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T00:00:00Z","timestamp":1673395200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T00:00:00Z","timestamp":1673395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"European Research Council","award":["LOPPRE (reference no. 819416)"],"award-info":[{"award-number":["LOPPRE (reference no. 819416)"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["grant no. 1176\/18"],"award-info":[{"award-number":["grant no. 1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Fradkin and Seymour (J Comb Theory Ser B 110:19\u201346, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including <jats:sc>Directed Feedback Arc Set<\/jats:sc>, <jats:sc>Directed Cutwidth<\/jats:sc> and <jats:sc>Optimal Linear Arrangement<\/jats:sc>, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk (in: Proceedings of the Algorithms\u2014ESA 2013\u201421st Annual European Symposium, Sophia Antipolis, France, September 2\u20134, 2013, pp. 505\u2013516, 2013), where to get the desired algorithms, it is enough to bound the number of <jats:italic>k<\/jats:italic>-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of <jats:italic>k<\/jats:italic>-cuts in transitive tournaments). Specifically, our main technical contribution is a combinatorial result that proves that the yes-instances of the problems (defined above) have a sub-exponential number of <jats:italic>k<\/jats:italic>-cuts. We prove this bound by using a combination of chromatic coding, inductive reasoning and exploiting the structural properties of these digraphs.<\/jats:p>","DOI":"10.1007\/s00453-022-01093-w","type":"journal-article","created":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T13:03:12Z","timestamp":1673442192000},"page":"2065-2086","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number"],"prefix":"10.1007","volume":"85","author":[{"given":"Pranabendu","family":"Misra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2212-1359","authenticated-orcid":false,"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"1093_CR1","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/1411509.1411513","volume":"55","author":"N Ailon","year":"2008","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55, 23:1-23:27 (2008)","journal-title":"J. ACM"},{"key":"1093_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1137\/050623905","volume":"20","author":"N Alon","year":"2006","unstructured":"Alon, N.: Ranking tournaments. SIAM J. Discrete Math. 20, 137\u2013142 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"1093_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Proceedings of the Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5\u201312, 2009, Part I, pp. 49\u201358 (2009)","DOI":"10.1007\/978-3-642-02927-1_6"},{"key":"1093_CR4","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1137\/0405027","volume":"5","author":"J Bang-Jensen","year":"1992","unstructured":"Bang-Jensen, J., Thomassen, C.: A polynomial algorithm for the 2-path problem for semicomplete digraphs. SIAM J. Discrete Math. 5, 366\u2013376 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"1093_CR5","unstructured":"Barbero, F., Paul, C., Pilipczuk, M.: Exploring the complexity of layout parameters in tournaments and semi-complete digraphs. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10\u201314, 2017, Warsaw, Poland, vol.\u00a080 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 70:1\u201370:13 (2017)"},{"key":"1093_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548306007887","volume":"16","author":"P Charbit","year":"2007","unstructured":"Charbit, P., Thomass\u00e9, S., Yeo, A.: The minimum feedback arc set problem is NP-hard for tournaments. Comb. Probab. Comput. 16, 1\u20134 (2007)","journal-title":"Comb. Probab. Comput."},{"key":"1093_CR7","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.jctb.2011.05.001","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M., Fradkin, A.O., Seymour, P.D.: Tournament immersion and cutwidth. J. Comb. Theory Ser. B 102, 93\u2013101 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1093_CR8","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jctb.2010.10.003","volume":"101","author":"M Chudnovsky","year":"2011","unstructured":"Chudnovsky, M., Seymour, P.D.: A well-quasi-order for tournaments. J. Comb. Theory Ser. B 101, 47\u201353 (2011)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1093_CR9","volume-title":"Graph Theory, Volume 173 of Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory, Volume 173 of Graduate Texts in Mathematics, 4th edn. Springer, New York (2012)","edition":"4"},{"key":"1093_CR10","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jda.2009.08.001","volume":"8","author":"M Dom","year":"2010","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R., Tru\u00df, A.: Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms 8, 76\u201386 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"1093_CR11","unstructured":"Feige, U.: Faster fast (feedback arc set in tournaments). CoRR arXiv:0911.5094 (2009)"},{"key":"1093_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Pilipczuk, M.: Jungles, bundles, and fixed parameter tractability. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6\u20138, 2013, pp. 396\u2013413 (2013)","DOI":"10.1137\/1.9781611973105.29"},{"key":"1093_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Pilipczuk, M.: Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. In: Proceedings of the Algorithms\u2014ESA 2013\u201421st Annual European Symposium, Sophia Antipolis, France, September 2\u20134, 2013, pp.\u00a0505\u2013516 (2013)","DOI":"10.1007\/978-3-642-40450-4_43"},{"key":"1093_CR14","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/j.jctb.2013.03.001","volume":"103","author":"AO Fradkin","year":"2013","unstructured":"Fradkin, A.O., Seymour, P.D.: Tournament pathwidth and topological containment. J. Comb. Theory Ser. B 103, 374\u2013384 (2013)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1093_CR15","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.jctb.2014.07.002","volume":"110","author":"AO Fradkin","year":"2015","unstructured":"Fradkin, A.O., Seymour, P.D.: Edge-disjoint paths in digraphs with bounded independence number. J. Comb. Theory Ser. B 110, 19\u201346 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1093_CR16","first-page":"181","volume":"21","author":"T Gallai","year":"1960","unstructured":"Gallai, T., Milgram, A.: Verallgemeinerung eines graphentheoretischen satzes von r\u00e9dei. Acta Sci. Math. 21, 181\u2013186 (1960)","journal-title":"Acta Sci. Math."},{"key":"1093_CR17","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In: Proceedings of the Algorithms and Computation\u201421st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15\u201317, 2010, Part I, pp. 3\u201314 (2010)","DOI":"10.1007\/978-3-642-17517-6_3"},{"key":"1093_CR18","doi-asserted-by":"crossref","unstructured":"Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11\u201313, 2007, pp. 95\u2013103 (2007)","DOI":"10.1145\/1250790.1250806"},{"key":"1093_CR19","unstructured":"Kumar, M., Lokshtanov, D.: Faster exact and parameterized algorithm for feedback vertex set in tournaments. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17\u201320, 2016, Orl\u00e9ans, France, Volume\u00a047 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp.\u00a049:1\u201349:13 (2016)"},{"key":"1093_CR20","unstructured":"Mnich, M., Williams, V.V., V\u00e9gh, L.A.: A 7\/3-approximation for feedback vertex sets in tournaments. In: 24th Annual European Symposium on Algorithms, ESA 2016, August 22\u201324, 2016, Aarhus, Denmark, pp. 67:1\u201367:14 (2016)"},{"key":"1093_CR21","unstructured":"Pilipczuk, M.: Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings. In: 30th International Symposium on Theoretical Aspects of Computer Science, STACS: February 27\u2013March 2, 2013, Kiel, Germany, Volume 20 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013, pp. 197\u2013208 (2013)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01093-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01093-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01093-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T05:58:01Z","timestamp":1687499881000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01093-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,11]]},"references-count":21,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1093"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01093-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,11]]},"assertion":[{"value":"10 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}