Fault Tolerant Directed Subgraphs with Applications in Kernelization

Given a vertex s in V(D), Baswana et al.~[STOC'16] presented a construction of H with O(2^k n) arcs in time O(2^k nm) where n=|V(D) and m=|E(D)| such that for any vertex v in V(D): if there exists a path from s to v in D-F, then there also exists a path from s to v in H-F. Additionally, they gave a tight matching lower bound. While the question of the improvement of the dependency on k arises for special classes of digraphs, an arguably more basic research direction concerns the dependency on n (for reachability between a pair of vertices s,t in V(D)) - which are the largest classes of digraphs where the dependency on n can be made sublinear, logarithmic or even constant?

Already for the simple classes of directed paths and tournaments, Omega(n) arcs are mandatory. Nevertheless, we prove that ``almost acyclicity'' suffices to eliminate the dependency on n entirely for a broad class of dense digraphs called bounded independence number digraphs. Also, the dependence in k is only a polynomial factor for this class of digraphs. In fact, our sparsification procedure extends to preserve parity-based reachability. Additionally, it finds notable applications in Kernelization: we prove that the classic Directed Feedback Arc Set problem as well as Directed Edge Odd Cycle Transversal admit polynomial kernels on bounded independence number digraphs. In fact, for any positive integer p, we can design a polynomial kernel for the problem of hitting all cycles of length r where r mod p =1.

---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.