Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams

DOI 10.1007/s00224-023-10136-w</link>zbMath 1530.05146</link>arXiv 1906.05458</link>MaRDI QID Q6185609</link>

Arijit Bishnu, Sudeshna Kolay, Saket Saurabh, Gopinath Mishra, Arijit Ghosh

Publication date: 8 January 2024

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1906.05458

zbMATH Keywords

vertex coverstreaming algorithmsFPTsubgraph deletion problemsminor deletion problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chordal editing is fixed-parameter tractable
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Finding odd cycle transversals.
• Chordal deletion is fixed-parameter tractable
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Structural results on matching estimation with applications to streaming
• Faster deterministic \textsc{Feedback Vertex Set}
• Hitting Forbidden Minors: Approximation and Kernelization
• Streaming Kernelization
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Planar Matching in Streams Revisited
• Communication Complexity
• Interval Deletion Is Fixed-Parameter Tractable
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
• The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
• Tight Bounds for Graph Problems in Insertion Streams
• Tight bounds for single-pass streaming complexity of the set cover problem
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Parameterized Algorithms

This page was built for publication: Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams