Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number

Area of Science:

• Graph theory
• Theoretical computer science
• Algorithm design

Background:

• Digraphs of bounded independence number generalize tournaments.
• These digraphs are structured for algorithmic exploitation.
• Parameterized algorithms for cut problems on tournaments are known.

Purpose of the Study:

• To demonstrate that cut problems solvable with sub-exponential parameterized algorithms on tournaments are also solvable on digraphs of bounded independence number.
• To extend the applicability of advanced algorithmic techniques to a broader class of graphs.
• To strengthen the algorithmic potential of digraphs with bounded independence number.

Main Methods:

• Leveraging the generic approach by Fomin and Pilipczuk for parameterized algorithms.
• Bounding the number of k-cuts in digraphs of bounded independence number by a sub-exponential function.
• Employing chromatic coding, inductive reasoning, and structural graph properties.

Main Results:

• Several cut problems, including Directed Feedback Arc Set, Directed Cutwidth, and Optimal Linear Arrangement, admit sub-exponential time parameterized algorithms on digraphs of bounded independence number.
• A key combinatorial result establishes a sub-exponential bound on the number of k-cuts for yes-instances of these problems.
• The findings generalize and extend previous algorithmic results from tournaments to digraphs of bounded independence number.

Conclusions:

• Digraphs of bounded independence number possess sufficient structure for advanced algorithmic techniques, particularly for cut problems.
• The study provides a theoretical foundation for developing efficient parameterized algorithms on these graph classes.
• This research significantly broadens the scope of problems amenable to sub-exponential time parameterized solutions in graph theory.