Fault tolerant subgraphs with applications in kernelization

Abstract

In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as fewest arcs/vertices as possible such that, after the failure of any set F of at most k ≥ 1 arcs, testing whether D-F has a certain property P is equivalent to testing whether H-F has that property. Here, reachability (or, more generally, distance preservation) is the most basic requirement to maintain to ensure that the network functions properly. Given a vertex s ∈ V(D), Baswana et al. [STOC'16] presented a construction of H with O(2^kn) arcs in time O(2^{k}nm) where n=|V(D)| and m= |E(D)| such that for any vertex v ∈ 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 ∈ 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, Ω(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 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 (DFAS) problem as well as Directed Edge Odd Cycle Transversal (DEOCT) (which, in sharp contrast to DFAS, is W[1]-hard on general digraphs) admit polynomial kernels on bounded independence digraphs. In fact, for any p ∈ N, we can design a polynomial kernel for the problem of hitting all cycles of length ℓ where (ℓ mod p = 1). As a complementary result, we prove that DEOCT is NP-hard on tournaments by establishing a combinatorial identity between the minimum size of a feedback arc set and the minimum size of an edge odd cycle transversal. In passing, we also improve upon the running time of the sub-exponential FPT algorithm for DFAS in digraphs of bounded independence number given by Misra et at. [FSTTCS 2018], and give the first sub-exponential FPT algorithm for DEOCT in digraphs of bounded independence number.