Partitioning a graph into small pieces with applications to path transversal

DOI10.1007/S10107-018-1255-7zbMath1452.68137arXiv1607.05122OpenAlexW3014552119MaRDI QIDQ2316611

Euiwoong Lee

Publication date: 6 August 2019

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

fixed parameter tractabilitygraph partitioningpath transversalsubgraph deletion

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (13)

Component order connectivity in directed graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Parameterized Complexity of Safe Set ⋮ Component order connectivity in directed graphs ⋮ Unnamed Item ⋮ On kernels for \(d\)-path vertex cover ⋮ Structural parameterizations of vertex integrity (best paper) ⋮ \(k\)-median/means with outliers revisited: a simple fpt approximation ⋮ Structural parameterizations of vertex integrity ⋮ Approximating the discrete time-cost tradeoff problem with bounded depth ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size ⋮ Vertex cover at distance on \(H\)-free graphs ⋮ Approximation algorithms for hitting subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational complexity of vertex integrity and component order connectivity
• Balanced graph partitioning
• A faster FPT algorithm for 3-path vertex cover
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• The \(k\)-separator problem: polyhedra, complexity and approximation results
• On the vertex \(k\)-path cover
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Fixed-Parameter and Approximation Algorithms: A New Look
• Detecting high log-densities
• Divide-and-conquer approximation algorithms via spreading metrics
• Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
• A new multilayered PCP and the hardness of hypergraph vertex cover
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Node-Deletion Problems on Bipartite Graphs
• The complexity of restricted spanning tree problems
• Fast Approximate Graph Partitioning Algorithms
• Approximation Algorithms for the 0-Extension Problem
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Inapproximability of H-Transversal/Packing
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: Partitioning a graph into small pieces with applications to path transversal