Streaming deletion problems parameterized by vertex cover

Jelle Oostveen; Erik Jan van Leeuwen

doi:10.1016/j.tcs.2023.114178

Streaming deletion problems parameterized by vertex cover

Jelle Oostveen^*
, Erik Jan van Leeuwen

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower bounds for the problems of Π-free Deletion, H-free Deletion, and the more specific forms of Cluster Vertex Deletion and Odd Cycle Transversal. We focus on the complexity in terms of the number of passes over the input stream, and the memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting.

Original language	English
Article number	114178
Pages (from-to)	1-25
Number of pages	25
Journal	Theoretical Computer Science
Volume	979
Early online date	15 Sept 2023
DOIs	https://doi.org/10.1016/j.tcs.2023.114178
Publication status	Published - 10 Nov 2023

Bibliographical note

Funding Information:
This work is based on the master thesis “Parameterized Algorithms in a Streaming Setting” by the first author. This work is partially supported by the NWO grant OCENW.KLEIN.114 (PACAN). An extended abstract of this article appeared in the proceedings of the 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), LNCS vol. 12867, Springer, 2021, pp. 413–426; see https://doi.org/10.1007/978-3-030-86593-1_29.The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Jelle Oostveen reports financial support was provided by NWO grant OCENW.KLEIN.114 (PACAN).

Funding Information:
This work is based on the master thesis “Parameterized Algorithms in a Streaming Setting” by the first author. This work is partially supported by the NWO grant OCENW.KLEIN.114 (PACAN) . An extended abstract of this article appeared in the proceedings of the 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), LNCS vol. 12867, Springer, 2021, pp. 413–426; see https://doi.org/10.1007/978-3-030-86593-1_29 .

Publisher Copyright:
© 2023 The Author(s)

Keywords

Graph streaming
Parameterized complexity
Vertex cover
Vertex deletion

Access to Document

10.1016/j.tcs.2023.114178Licence: CC BY

1-s2.0-S0304397523004917-mainFinal published version, 760 KBLicence: CC BY

Cite this

@article{37622f91c2364925bbba35c048d68062,

title = "Streaming deletion problems parameterized by vertex cover",

abstract = "Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower bounds for the problems of Π-free Deletion, H-free Deletion, and the more specific forms of Cluster Vertex Deletion and Odd Cycle Transversal. We focus on the complexity in terms of the number of passes over the input stream, and the memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting.",

keywords = "Graph streaming, Parameterized complexity, Vertex cover, Vertex deletion",

author = "Jelle Oostveen and \{van Leeuwen\}, \{Erik Jan\}",

note = "Funding Information: This work is based on the master thesis “Parameterized Algorithms in a Streaming Setting” by the first author. This work is partially supported by the NWO grant OCENW.KLEIN.114 (PACAN). An extended abstract of this article appeared in the proceedings of the 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), LNCS vol. 12867, Springer, 2021, pp. 413–426; see https://doi.org/10.1007/978-3-030-86593-1\_29.The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Jelle Oostveen reports financial support was provided by NWO grant OCENW.KLEIN.114 (PACAN). Funding Information: This work is based on the master thesis “Parameterized Algorithms in a Streaming Setting” by the first author. This work is partially supported by the NWO grant OCENW.KLEIN.114 (PACAN) . An extended abstract of this article appeared in the proceedings of the 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), LNCS vol. 12867, Springer, 2021, pp. 413–426; see https://doi.org/10.1007/978-3-030-86593-1\_29 . Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2023",

month = nov,

day = "10",

doi = "10.1016/j.tcs.2023.114178",

language = "English",

volume = "979",

pages = "1--25",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Streaming deletion problems parameterized by vertex cover

AU - Oostveen, Jelle

AU - van Leeuwen, Erik Jan

N1 - Funding Information: This work is based on the master thesis “Parameterized Algorithms in a Streaming Setting” by the first author. This work is partially supported by the NWO grant OCENW.KLEIN.114 (PACAN). An extended abstract of this article appeared in the proceedings of the 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), LNCS vol. 12867, Springer, 2021, pp. 413–426; see https://doi.org/10.1007/978-3-030-86593-1_29.The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Jelle Oostveen reports financial support was provided by NWO grant OCENW.KLEIN.114 (PACAN). Funding Information: This work is based on the master thesis “Parameterized Algorithms in a Streaming Setting” by the first author. This work is partially supported by the NWO grant OCENW.KLEIN.114 (PACAN) . An extended abstract of this article appeared in the proceedings of the 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), LNCS vol. 12867, Springer, 2021, pp. 413–426; see https://doi.org/10.1007/978-3-030-86593-1_29 . Publisher Copyright: © 2023 The Author(s)

PY - 2023/11/10

Y1 - 2023/11/10

N2 - Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower bounds for the problems of Π-free Deletion, H-free Deletion, and the more specific forms of Cluster Vertex Deletion and Odd Cycle Transversal. We focus on the complexity in terms of the number of passes over the input stream, and the memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting.

AB - Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower bounds for the problems of Π-free Deletion, H-free Deletion, and the more specific forms of Cluster Vertex Deletion and Odd Cycle Transversal. We focus on the complexity in terms of the number of passes over the input stream, and the memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting.

KW - Graph streaming

KW - Parameterized complexity

KW - Vertex cover

KW - Vertex deletion

UR - https://www.scopus.com/pages/publications/85171990264

U2 - 10.1016/j.tcs.2023.114178

DO - 10.1016/j.tcs.2023.114178

M3 - Article

SN - 0304-3975

VL - 979

SP - 1

EP - 25

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 114178

ER -

Streaming deletion problems parameterized by vertex cover

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this