Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams
share
In this work, we initiate a systematic study of parameterized streaming complexity of graph deletion problems: F-Subgraph Deletion, F-Minor Deletion and Cluster Vertex Deletion in the four most well-studied streaming models: the EA (edge arrival), DEA (dynamic edge arrival), VA (vertex arrival) and AL (adjacency list) models. We also consider the streaming complexities of a collection of widely-studied problems that are special variants of F-Subgraph Deletion, namely Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal, Triangle Deletion, and Cluster Vertex Deletion. Except for the Triangle Deletion and Cluster Vertex Deletion problems, we show that none of the other problems have space-efficient streaming algorithms when the problems are parameterized by k, the solution size. In fact, we show that these problems admit Ω(n n) lower bounds in all the four models stated above. This improves the lower bounds given by Chitnis et al. (SODA'16) for the EA model. For the Triangle Deletion and Cluster Vertex Deletion problems, the question of lower bounds for the problems parameterized by k is open for the AL model. For all other models, we show an improved lower bound of Ω(n n) for Triangle Deletion. With regards to Cluster Vertex Deletion, we extend the results of Chitnis et al. (SODA'16) in the EA model to the DEA and VA models. We exploit the power of parameterization - a usual approach taken in parameterized algorithms - to study a problem with respect to parameters greater than the solution size or consider some structural parameters. Parameterized by vertex cover size K, some of these problems on some of the graph streaming models do not admit space-efficient streaming algorithms, while it does so for others
READ FULL TEXT