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

Fradkin and Seymour (J Comb Theory Ser B 110:19-46, 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.

Parameterized Complexity of Directed Spanner Problems.

We initiate the parameterized complexity study of minimum -spanner problems on directed graphs. For a positive integer , a multiplicative -spanner of a (directed) graph is a spanning subgraph such that the distance between any two vertices in is at most times the distance between these vertices in , that is, keeps the distances in up to the distortion (or stretch) factor . An additive -spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter , that is, the distances in and differ by at most .