Losing Treewidth by Separating Subsets

DOI10.1137/1.9781611975482.104MaRDI QIDQ5236288zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michał Włodarczyk

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: We study the problem of deleting the smallest set $S$ of vertices (resp. edges) from a given graph $G$ such that the induced subgraph (resp. subgraph) $GsetminusS$ belongs to some class $mathcalH$. We consider the case where graphs in $mathcalH$ have treewidth bounded by $t$, and give a general framework to obtain approximation algorithms for both vertex and edge-deletion settings from approximation algorithms for certain natural graph partitioning problems called $k$-Subset Vertex Separator and $k$-Subset Edge Separator, respectively. For the vertex deletion setting, our framework combined with the current best result for $k$-Subset Vertex Separator, yields a significant improvement in the approximation ratios for basic problems such as $k$-Treewidth Vertex Deletion and Planar-$F$ Vertex Deletion. Our algorithms are simpler than previous works and give the first uniform approximation algorithms under the natural parameterization. For the edge deletion setting, we give improved approximation algorithms for $k$-Subset Edge Separator combining ideas from LP relaxations and important separators. We present their applications in bounded-degree graphs, and also give an APX-hardness result for the edge deletion problems.

Recommendations

• Tree size reduction with keeping distinguishability
• Treewidth of grid subsets
• Subset counting in trees
• On the Complexity of Extracting Subtree with Keeping Distinguishability
• On tree-partition-width
• Space-efficient vertex separators for treewidth
• Finding small separators in linear time via treewidth reduction
• Separating decision tree complexity from subcube partition complexity

Cited in

(21)

• Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• On the feedback number of 3-uniform linear extremal hypergraphs
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• On algorithms employing treewidth for L-bounded cut problems
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• scientific article; zbMATH DE number 7525474 (Why is no real title available?)
• Data-compression for parametrized counting problems on sparse graphs
• On the fixed-parameter tractability of capacitated clustering
• Separating layered treewidth and row treewidth
• scientific article; zbMATH DE number 7765420 (Why is no real title available?)
• Kernelization for feedback vertex set via elimination distance to a forest
• On maximum bipartite matching with separation
• Justifying groups in multiwinner approval voting
• k-median/means with outliers revisited: a simple fpt approximation
• Search-space reduction via essential vertices
• Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
• A constant-factor approximation for weighted bond cover
• On the generalized mean densest subgraph problem: complexity and algorithms
• Outer-planar vertex deletion on AT-free graphs
• On bounded-degree vertex deletion parameterized by treewidth

This page was built for publication: Losing Treewidth by Separating Subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236288)