Inapproximability of $H$-Transversal/Packing
type: Item
instance of: scholarly article
title: Inapproximability of $H$-Transversal/Packing
zbMATH Open document ID: 1371.68099
DOI: 10.1137/16M1070670
author: Euiwoong Lee
author: Venkatesan Guruswami
published in: SIAM Journal on Discrete Mathematics
publication date: 2017-08-14T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6760178
zbMATH Keywords: hardness of approximation
zbMATH Keywords: graph transversal
zbMATH Keywords: graph packing
MaRDI profile type: Publication
cites work: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
cites work: Logarithmic hardness of the undirected edge-disjoint paths problem
cites work: Q3002828
cites work: Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
cites work: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
cites work: Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
cites work: ON DISJOINT CYCLES
cites work: Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
cites work: Approximation resistance from pairwise independent subgroups
cites work: Q4448744
cites work: Approximation algorithms and hardness results for the clique packing problem
cites work: A fixed-parameter algorithm for the directed feedback vertex set problem
cites work: Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
cites work: Approximation hardness of dominating set problems in bounded degree graphs
cites work: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
cites work: Subset Feedback Vertex Set Is Fixed-Parameter Tractable
cites work: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
cites work: On the hardness of approximating minimum vertex cover
cites work: Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
cites work: Algorithms for finding clique-transversals of graphs
cites work: Covering the cliques of a graph with vertices
cites work: Divide-and-conquer approximation algorithms via spreading metrics
cites work: Approximating minimum feedback sets and multicuts in directed graphs
cites work: Approximability of Packing Disjoint Cycles
cites work: Inapproximability of H-Transversal/Packing
cites work: Algorithmic aspects of clique-transversal and clique-independent sets
cites work: The \(K_r\)-packing problem
cites work: On the complexity of approximating \(k\)-set packing
cites work: Packing \(r\)-cliques in weighted chordal graphs
cites work: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
cites work: On the power of unique 2-prover 1-round games
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: On the Complexity of General Graph Factor Problems
cites work: Approximating Maximum Subgraphs without Short Cycles
cites work: Approximation algorithms for cycle packing problems
cites work: Weighted maximum-clique transversal sets of graphs
cites work: Partitioning a Graph into Small Pieces with Applications to Path Transversal
cites work: The approximation of maximum subgraph problems
cites work: Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
cites work: On packing shortest cycles in graphs
cites work: Packing directed circuits fractionally
cites work: Clique-transversal sets and clique-coloring in planar graphs
cites work: Q3191594
cites work: Covering all cliques of a graph
cites work: Combinatorial and computational aspects of graph packing and graph decomposition
cites work: Edge-Disjoint Cliques in Graphs with High Minimum Degree
cites work: Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
description: scientific article; zbMATH DE number 6760178