2026-07-21T12:47:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9934 2024-03-06T10:45:08Z ddc:004 open_access

Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number Misra, Pranabendu Saurabh, Saket Sharma, Roohani Zehavi, Meirav sub-exponential fixed-parameter tractable algorithms directed feedback arc set directed cutwidth optimal linear arrangement bounded independence number digraph Fradkin and Seymour [Journal of Combinatorial Graph Theory, Series B, 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 Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk [ESA, 2013], where to get the desired algorithms, it is enough to bound the number of k-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of k-cuts in transitive tournaments). Specifically, our main technical contribution is that the yes-instances of the problems above have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, an inductive argument and structural properties of the digraphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pranabendu Misra and Saket Saurabh and Roohani Sharma and Meirav Zehavi 2018 Is Part Of LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2018.35 urn:nbn:de:0030-drops-99341 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.35 eng https://creativecommons.org/licenses/by/3.0/legalcode