Inapproximability of $H$-Transversal/Packing
From MaRDI portal
Publication:5348212
DOI10.1137/16M1070670zbMath1371.68099MaRDI QIDQ5348212
Euiwoong Lee, Venkatesan Guruswami
Publication date: 14 August 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (8)
Improved approximation algorithms for hitting 3-vertex paths ⋮ Strong hardness of approximation for tree transversals ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ On the \(d\)-claw vertex deletion problem ⋮ Unnamed Item ⋮ On the \(d\)-claw vertex deletion problem ⋮ Approximation algorithms for hitting subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Weighted maximum-clique transversal sets of graphs
- Combinatorial and computational aspects of graph packing and graph decomposition
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- On the hardness of approximating minimum vertex cover
- Packing \(r\)-cliques in weighted chordal graphs
- Algorithms for finding clique-transversals of graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- On packing shortest cycles in graphs
- Covering all cliques of a graph
- Covering the cliques of a graph with vertices
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Approximating minimum feedback sets and multicuts in directed graphs
- Packing directed circuits fractionally
- Algorithmic aspects of clique-transversal and clique-independent sets
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Clique-transversal sets and clique-coloring in planar graphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- On the complexity of approximating \(k\)-set packing
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Divide-and-conquer approximation algorithms via spreading metrics
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- On the Complexity of General Graph Factor Problems
- Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
- Edge-Disjoint Cliques in Graphs with High Minimum Degree
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Logarithmic hardness of the undirected edge-disjoint paths problem
- On the power of unique 2-prover 1-round games
- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- ON DISJOINT CYCLES
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- Partitioning a Graph into Small Pieces with Applications to Path Transversal
- The approximation of maximum subgraph problems
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Inapproximability of H-Transversal/Packing
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Approximability of Packing Disjoint Cycles
- Approximation resistance from pairwise independent subgroups
- Approximating Maximum Subgraphs without Short Cycles
- Approximation algorithms and hardness results for the clique packing problem
- The \(K_r\)-packing problem
This page was built for publication: Inapproximability of $H$-Transversal/Packing
