Algorithmic Properties of Sparse Digraphs

摘要: The notions of bounded expansion and nowhere denseness have been applied very successfully in algorithmic graph theory. We study the corresponding directed crownfulness on graphs. show that many tools were developed for undirected classes can, with some care, also be their counterparts, thereby we highlight a rich structure theory classes. More specifically, Steiner tree problem is fixed-parameter tractable any class parameterized by number $k$ non-terminals plus maximal diameter $s$ strongly connected component subgraph induced terminals. Our result generalizes Jones et al., who proved fixed parameter digraphs degeneracy if set terminals required to acyclic. We furthermore prove every integer $r\geq 1$, distance-$r$ dominating can approximated up factor $O(\log k)$ $O(k\cdot \log expansion, where denotes size an optimal solution. If furthermore, crownful, are able compute polynomial kernel sets. Polynomial kernels this not known exist other existing digraph measure sparse