Streaming deletion problems Parameterized by vertex cover

DOI10.1016/j.tcs.2023.114178OpenAlexW3215145351MaRDI QIDQ6057830

Jelle J. Oostveen, Erik Jan van Leeuwen

Publication date: 26 October 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114178

zbMATH Keywords

vertex coverparameterized complexityvertex deletiongraph streaming

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting small induced subgraphs efficiently
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Subgraph isomorphism in graph classes
• Finding odd cycle transversals.
• On the complexity of fixed parameter clique and dominating set
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Parameterized complexity of finding regular induced subgraphs
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fixed parameter tractability of graph deletion problems over data streams
• Faster parameterized algorithm for cluster vertex deletion
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• On the parameterized complexity of graph modification to first-order logic properties
• On the complexity of various parameterizations of common induced subgraph isomorphism
• Maximum common induced subgraph parameterized by vertex cover
• On graph problems in a semi-streaming model
• Counting and Detecting Small Subgraphs via Equations
• Streaming Kernelization
• A simple linear-time algorithm for computing the center of an interval graph
• A Linear Recognition Algorithm for Cographs
• Finding a Minimum Circuit in a Graph
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Kernelization Lower Bounds by Cross-Composition
• Finding Four-Node Subgraphs in Triangle Time
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Parameterized Algorithms
• Slightly Superexponential Parameterized Problems
• Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles
• Towards a theory of parameterized streaming algorithms
• On the complexity of \(k\)-SAT