2013/08/15 by Rajesh Chitnis, Chitnis, Rajesh, MohammadTaghi Hajiaghayi +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1308.3520
openalex publication_date 2013/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A Fixed-Parameter Tractable (\FPT) ρ-approximation algorithm for a minimization (resp. maximization) parameterized problem P is an FPT algorithm that, given an instance (x, k)∈ P computes a solution of cost at most k ⋅ ρ(k) (resp. k/ρ(k)) if a solution of cost at most (resp. at least) k exists; otherwise the output can be arbitrary. For well-known intractable problems such as the W[1]-hard Clique and W[2]-hard Set Cover problems, the natural question is whether we can get any \FPT-approximation. It is widely believed that both Clique and Set-Cover admit no FPT ρ-approximation algorithm, for any increasing function ρ. Assuming standard conjectures such as the Exponential Time Hypothesis (ETH) \citeeth-paturi and the Projection Games Conjecture (PGC) \citer3, we make the first progress towards proving this conjecture by showing that 1. Under the ETH and PGC, there exist constants F1, F2 >0 such that the Set Cover problem does not admit an FPT approximation algorithm with ratio kF1 in 2^kF2⋅ poly(N,M) time, where N is the size of the universe and M is the number of sets. 2. Unless \NP⊆ \SUBEXP, for every 1> δ> 0 there exists a constant F(δ)>0 such that Clique has no FPT cost approximation with ratio k1-δ in 2^kF⋅ poly(n) time, where n is the number of vertices in the graph. In the second part of the paper we consider various W[1]-hard problems such as \dst, \dsf, Directed Steiner Network and \mec. For all these problem we give polynomial time f(OPT)-approximation algorithms for some small function f (the largest approximation ratio we give is OPT2).