{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T05:19:58Z","timestamp":1702012798714},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,9,20]],"date-time":"2023-09-20T00:00:00Z","timestamp":1695168000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,20]],"date-time":"2023-09-20T00:00:00Z","timestamp":1695168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,12]]},"abstract":"Abstract<\/jats:title>In the study of parameterized streaming complexity on graph problems, the main goal is to design streaming algorithms for parameterized problems such that $$\\mathcal {O}(f(k) \\log ^{\\mathcal {O}(1)} n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n f<\/mml:mi>\n \n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n log<\/mml:mo>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> space is enough, where f<\/jats:italic> is an arbitrary computable function depending only on the parameter k<\/jats:italic>. However, in the past few years very few positive results have been established. Most of the graph problems that do have streaming algorithms of the above nature are ones where localized checking is required, like Vertex Cover<\/jats:sc> or Maximum Matching<\/jats:sc> parameterized by the size k<\/jats:italic> of the solution we are seeking. Chitnis et al. (SODA\u201916) have shown that many important parameterized problems that form the backbone of traditional parameterized complexity are known to require $$\\Omega (n)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits of storage for any streaming algorithm; e.g. Feedback Vertex Set<\/jats:sc>, Even Cycle Transversal<\/jats:sc>, Odd Cycle Transversal<\/jats:sc>, Triangle Deletion<\/jats:sc> or the more general $$\\mathcal{F}$$<\/jats:tex-math>\n F<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Subgraph Deletion<\/jats:sc> when parameterized by solution size k<\/jats:italic>. Our contribution lies in overcoming the obstacles to efficient parameterized streaming algorithms in graph deletion problems by utilizing the power of parameterization. We focus on the vertex cover size K<\/jats:italic> as the parameter for the parameterized graph deletion problems we consider. In this work, we consider the four most well-studied streaming models: the Ea<\/jats:sc>, Dea<\/jats:sc>, Va<\/jats:sc> (vertex arrival) and Al<\/jats:sc> (adjacency list) models. Surprisingly, the consideration of vertex cover size K<\/jats:italic> in the different models leads to a classification of positive and negative results for problems like $$\\mathcal{F}$$<\/jats:tex-math>\n F<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Subgraph Deletion<\/jats:sc> and $$\\mathcal{F}$$<\/jats:tex-math>\n F<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Minor Deletion<\/jats:sc>.<\/jats:p>","DOI":"10.1007\/s00224-023-10136-w","type":"journal-article","created":{"date-parts":[[2023,9,20]],"date-time":"2023-09-20T09:01:46Z","timestamp":1695200506000},"page":"1241-1267","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams"],"prefix":"10.1007","volume":"67","author":[{"given":"Arijit","family":"Bishnu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arijit","family":"Ghosh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gopinath","family":"Mishra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,20]]},"reference":[{"key":"10136_CR1","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y.: Tight Bounds for Single-pass Streaming Complexity of the Set Cover Problem. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp 698\u2013711 (2016)","DOI":"10.1145\/2897518.2897576"},{"key":"10136_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, D., McGregor, A., Phillips, J.M., Venkatasubramanian, S., Zhu, Z.: Spatial Scan Statistics Approximations and Performance Study. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 24\u201333 (2006)","DOI":"10.1145\/1150402.1150410"},{"issue":"1","key":"10136_CR3","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s00453-018-0449-y","volume":"81","author":"M Bury","year":"2019","unstructured":"Bury, M., Grigorescu, E., McGregor, A., Monemizadeh, M., Schwiegelshohn, C., Vorotnikova, S., Zhou, S.: Structural Results on Matching Estimation with Applications to Streaming. Algorithmica 81(1), 367\u2013392 (2019)","journal-title":"Algorithmica"},{"key":"10136_CR4","unstructured":"Bishnu, A., Ghosh, A., Mishra, G., Sen, S.: On the streaming complexity of fundamental geometric problems. CoRR, abs\/1803.06875 (2018)"},{"issue":"4","key":"10136_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed-Parameter Tractability of Graph Modification Problems for Hereditary Properties. Inf. Process. Lett. 58(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"10136_CR6","doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Cormode, G., Esfandiari, H., Hajiaghayi, M., Monemizadeh, M.: Brief Announcement New Streaming Algorithms for Parameterized Maximal Matching & Beyond. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA, pp 56\u201358 (2015)","DOI":"10.1145\/2755573.2755618"},{"key":"10136_CR7","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp 1326\u20131344 (2016)","DOI":"10.1137\/1.9781611974331.ch92"},{"key":"10136_CR8","doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Cormode, G., Hajiaghayi, M.T., Monemizadeh, M.: Parameterized Streaming: Maximal Matching and Vertex Cover. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp 1234\u20131251 (2015)","DOI":"10.1137\/1.9781611973730.82"},{"key":"10136_CR9","unstructured":"Cormode, G., Dark, J., Konrad, C.: Independent Sets in Vertex-Arrival Streams. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, ICALP, pp 45:1\u201345:14 (2019)"},{"key":"10136_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, 1st edn. Springer Publishing Company, Incorporated (2015)","edition":"1"},{"key":"10136_CR11","unstructured":"Cormode, G., Jowhari, H., Monemizadeh, M., Muthukrishnan, S.: The Sparse Awakens Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In Proceedings of the 25th Annual European Symposium on Algorithms, ESA, volume\u00a087, pp 29:1\u201329:15 (2017)"},{"key":"10136_CR12","doi-asserted-by":"crossref","unstructured":"Cao, Y., Marx, D.: Interval Deletion Is Fixed-Parameter Tractable. ACM Trans. Algorithms, 11(3):21:1\u201321:35 (2015)","DOI":"10.1145\/2629595"},{"issue":"1","key":"10136_CR13","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s00453-015-0014-x","volume":"75","author":"Y Cao","year":"2016","unstructured":"Cao, Y., Marx, D.: Chordal Editing is Fixed-Parameter Tractable. Algorithmica 75(1), 118\u2013137 (2016)","journal-title":"Algorithmica"},{"issue":"4","key":"10136_CR14","first-page":"1","volume":"14","author":"H Esfandiari","year":"2018","unstructured":"Esfandiari, H., Hajiaghayi, M., Liaghat, V., Monemizadeh, M., Onak, K.: Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. ACM Trans. Alg. 14(4), 1\u201323 (2018)","journal-title":"ACM Trans. Alg."},{"issue":"2","key":"10136_CR15","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1016\/j.jcss.2013.09.004","volume":"80","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Jansen, B.M.P., Pilipczuk, M.: Preprocessing subgraph and minor problems When does a small vertex cover help? J. Comput. Syst. Sci. 80(2), 468\u2013495 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"10136_CR16","doi-asserted-by":"crossref","unstructured":"Fafianie, S., Kratsch, S.: Streaming kernelization. In Proceedings of the 39th International Symposium on Math. Found. Comput. Sci., MFCS, pp 275\u2013286 (2014)","DOI":"10.1007\/978-3-662-44465-8_24"},{"issue":"1","key":"10136_CR17","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1137\/140997889","volume":"30","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Philip, G., Saurabh, S.: Hitting Forbidden Minors Approximation and Kernelization. SIAM J. Discret. Math. 30(1), 383\u2013410 (2016)","journal-title":"SIAM J. Discret. Math."},{"key":"10136_CR18","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-Deletion Approximation, Kernelization and Optimal FPT Algorithms. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pP 470\u2013479 (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"10136_CR19","unstructured":"Guruswami, V., Velingker, A., Velusamy, S.: Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM, pP 8:1\u20138:19 (2017)"},{"key":"10136_CR20","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Khanna, S., Sudan, M., Velingker, A.: $$1+\\Omega (1)$$ approximation to MAX-CUT Requires Linear Space. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp 1703\u20131722 (2017)","DOI":"10.1137\/1.9781611974782.112"},{"key":"10136_CR21","doi-asserted-by":"crossref","unstructured":"Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions. ACM Trans. Algorithms, 12(2):21:1\u201321:41 (2016)","DOI":"10.1145\/2797140"},{"key":"10136_CR22","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York, NY, USA (1997)"},{"issue":"10","key":"10136_CR23","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1016\/j.ipl.2014.05.001","volume":"114","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Pilipczuk, M.: Faster deterministic Feedback Vertex Set. Inf. Process. Lett. 114(10), 556\u2013560 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"10136_CR24","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D Marx","year":"2010","unstructured":"Marx, D.: Chordal Deletion is Fixed-Parameter Tractable. Algorithmica 57(4), 747\u2013768 (2010)","journal-title":"Algorithmica"},{"issue":"1","key":"10136_CR25","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph Stream Algorithms A Survey. SIGMOD Record 43(1), 9\u201320 (2014)","journal-title":"SIGMOD Record"},{"key":"10136_CR26","volume-title":"Planar Matching in Streams Revisited","author":"A McGregor","year":"2016","unstructured":"McGregor, A., Vorotnikova, S.: Planar Matching in Streams Revisited. In APPROX\/RANDOM, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"10136_CR27","volume-title":"A Simple, Space-Efficient","author":"A McGregor","year":"2018","unstructured":"McGregor, A., Vorotnikova, S.: A Simple, Space-Efficient. Streaming Algorithm for Matchings in Low Arboricity Graphs, In SOSA (2018)"},{"key":"10136_CR28","doi-asserted-by":"crossref","unstructured":"McGregor, A., Vorotnikova, S., Vu, H.T.: Better Algorithms for Counting Triangles in Data Streams. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pp 401\u2013411 (2016)","DOI":"10.1145\/2902251.2902283"},{"issue":"4","key":"10136_CR29","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"BA Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"10136_CR30","unstructured":"Sun, X., Woodruff, D.P.: Tight Bounds for Graph Problems in Insertion Streams. In Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, pp 435\u2013448 (2015)"},{"key":"10136_CR31","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A $$4k^{2}$$ Kernel for Feedback Vertex Set. ACM Trans. Algorithms, 6(2):32:1\u201332:8 (2010)","DOI":"10.1145\/1721837.1721848"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10136-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10136-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10136-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T01:03:52Z","timestamp":1701997432000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10136-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,20]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10136"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10136-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,20]]},"assertion":[{"value":"12 June 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}