Meta-theorems for Parameterized Streaming Algorithms‡

e streaming model was introduced to parameterized complexity independently by Fafianie and Kratsch [MFCS14] and by Chitnis, Cormode, Hajiaghayi and Monemizadeh [SODA15]. Subsequently, it was broadened by Chitnis, Cormode, Esfandiari, Hajiaghayi and Monemizadeh [SPAA15] and by Chitnis, Cormode, Esfandiari, Hajiaghayi, McGregor, Monemizadeh and Vorotnikova [SODA16]. Despite its strong motivation, the applicability of the streaming model to central problems in parameterized complexity has remained, for almost a decade, quite limited. Indeed, due to simple Ω(n)-space lower bounds for many of these problems, the k O(1) • polylog(n)-space requirement in the model is too strict.

us, we explore semi-streaming algorithms for parameterized graph problems, and present the first systematic study of this topic. Crucially, we aim to construct succinct representations of the input on which optimal post-processing time complexity can be achieved.

• We devise meta-theorems specifically designed for parameterized streaming and demonstrate their applicability by obtaining the first k O(1) • n • polylog(n)-space streaming algorithms for wellstudied problems such as Feedbac Vertex Set on Tournaments, Cluster Vertex Deletion, Proper Interval Vertex Deletion and Bloc Vertex Deletion. In the process, we demonstrate a fundamental connection between semi-streaming algorithms for recognizing graphs in a graph class H and semi-streaming algorithms for the problem of vertex deletion into H.