Fixed parameter tractability of graph deletion problems over data streams. (English) Zbl 07336142
Kim, Donghyun (ed.) et al., Computing and combinatorics. 26th international conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12273, 652-663 (2020).
Summary: The study of parameterized streaming complexity on graph problems was initiated by Fafianie et al. (MFCS’14) and Chitnis et al. (SODA’15 and SODA’16). In this work, we initiate a systematic study of parameterized streaming complexity of graph deletion problems – \(\mathcal{F}\)-Subgraph deletion, \(\mathcal{F}\)-Minor 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. Our main conceptual contribution is to overcome the obstacles to efficient parameterized streaming algorithms by utilizing the power of parameterization. We focus on the vertex cover size \(K\) as the parameter for the parameterized graph deletion problems we consider. At the same time, most of the previous work in parameterized streaming complexity was restricted to the Ea (edge arrival) or Dea (dynamic edge arrival) models. In this work, we consider the four most well-studied streaming models: the Ea, Dea, Va (vertex arrival) and Al (adjacency list) models.
For the entire collection see [Zbl 1458.68009].
For the entire collection see [Zbl 1458.68009].
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
References:
| [1] | Assadi, S., Khanna, S., Li, Y.: Tight bounds for single-pass streaming complexity of the set cover problem. In: STOC, pp. 698-711 (2016) · Zbl 1373.68250 |
| [2] | Bishnu, A., Ghosh, A., Kolay, S., Mishra, G., Saurabh, S.: Fixed-parameter tractability of graph deletion problems over data streams. CoRR, abs/1906.05458 (2019) · Zbl 07336142 |
| [3] | Bury, M., Structural results on matching estimation with applications to streaming, Algorithmica, 81, 1, 367-392 (2019) · Zbl 1412.68163 · doi:10.1007/s00453-018-0449-y |
| [4] | Chitnis, R., Cormode, G.: Towards a theory of parameterized streaming algorithms. In: IPEC, vol. 148, pp. 7:1-7:15 (2019) · Zbl 07650215 |
| [5] | Chitnis, R., et al.: Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In: SODA, pp. 1326-1344 (2016) · Zbl 1409.68341 |
| [6] | Chitnis, R.H., Cormode, G., Esfandiari, H., Hajiaghayi, M., Monemizadeh, M.: Brief announcement: new streaming algorithms for parameterized maximal matching & beyond. In: SPAA, pp. 56-58 (2015) |
| [7] | Chitnis, R.H., Cormode, G., Hajiaghayi, M.T., Monemizadeh, M.: Parameterized streaming: maximal matching and vertex cover. In: SODA, pp. 1234-1251 (2015) · Zbl 1372.68207 |
| [8] | Cormode, G., Dark, J., Konrad, C.: Independent sets in vertex-arrival streams. In: ICALP, pp. 45:1-45:14 (2019) · Zbl 1517.68285 |
| [9] | Cormode, G., Jowhari, H., Monemizadeh, M., Muthukrishnan, S.: The sparse awakens: streaming algorithms for matching size estimation in sparse graphs. In: 25th Annual European Symposium on Algorithms, ESA 2017. LIPIcs, vol. 87, pp. 29:1-29:15 (2017) · Zbl 1442.68273 |
| [10] | Cygan, M., Parameterized Algorithms (2015), Heidelberg: Springer, Heidelberg · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3 |
| [11] | Esfandiari, H.; Hajiaghayi, M.; Liaghat, V.; Monemizadeh, M.; Onak, K., Streaming algorithms for estimating the matching size in planar graphs and beyond, ACM Trans. Algorithms, 14, 4, 1-23 (2018) · Zbl 1454.68191 · doi:10.1145/3230819 |
| [12] | Fafianie, S., Kratsch, S.: Streaming kernelization. In: MFCS, pp. 275-286 (2014) · Zbl 1426.68120 |
| [13] | Fomin, FV; Jansen, BMP; Pilipczuk, M., Preprocessing subgraph and minor problems: When does a small vertex cover help?, JCSS, 80, 2, 468-495 (2014) · Zbl 1277.68095 |
| [14] | Guruswami, V., Velingker, A., Velusamy, S.: Streaming complexity of approximating max 2CSP and max acyclic subgraph. In: APPROX/RANDOM, pp. 8:1-8:19 (2017) · Zbl 1467.68064 |
| [15] | Kapralov, M., Khanna, S., Sudan, M., Velingker, A.: \(1+\omega (1)\) approximation to MAX-CUT requires linear space. In: SODA, pp. 1703-1722 (2017) · Zbl 1410.68169 |
| [16] | McGregor, A., Graph stream algorithms: a survey, SIGMOD Rec., 43, 1, 9-20 (2014) · doi:10.1145/2627692.2627694 |
| [17] | McGregor, A., Vorotnikova, S.: Planar matching in streams revisited. In: APPROX/RANDOM, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016) · Zbl 1398.68682 |
| [18] | McGregor, A., Vorotnikova, S.: A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs. In: SOSA (2018) · Zbl 1433.68622 |
| [19] | McGregor, A., Vorotnikova, S., Vu, H.T.: Better algorithms for counting triangles in data streams. In: PODS, pp. 401-411 (2016) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
