Abstract
Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between these different frameworks. In particular, whether Independent Set would be better approximable once endowed with subexponential-time or FPT-time is a central question. In this article, we provide new insights to this question using two complementary approaches; the former makes a strong link between the linear PCP conjecture and inapproximability; the latter builds a class of equivalent problems under approximation in subexponential time.
Research supported by the French Agency for Research under the DEFIS program TODO, ANR-09-EMER-010.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Approximation Algorithm
- Vertex Cover
- Parameterized Approximation Algorithm
- Inapproximability Result
- Subexponential Time
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bonnet, É., Escoffier, B., Kim, E.J., Paschos, V.T.: On Subexponential and FPTtime Inapproximability. CoRR abs/1211.6656 (2012)
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of approximation problems. J. ACM 45, 501–555 (1998)
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proc. STOC 2006, pp. 681–690 (2006)
Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)
Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39, 546–563 (2009)
Bourgeois, N., Escoffier, B., Paschos, V.T.: Efficient approximation of min coloring by moderately exponential algorithms. Inform. Process. Lett. 109, 950–954 (2009)
Bourgeois, N., Escoffier, B., Paschos, V.T.: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Appl. Math. 159, 1954–1970 (2011)
Cai, L., Chen, J.: On fixed-parameter tractability and approximability of NP optimization problems. J. Comput. System Sci. 54, 465–474 (1997)
Cai, L., Huang, X.: Fixed-parameter approximation: Conceptual framework and approximability results. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 96–108. Springer, Heidelberg (2006)
Cai, L., Juedes, D.W.: On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67(4), 789–807 (2003)
Chen, Y.-J., Grohe, M., Grüber, M.: On parameterized approximability. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 109–120. Springer, Heidelberg (2006)
Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. System Sci. 72, 1346–1367 (2006)
Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theoret. Comput. Sci. 411, 3701–3713 (2010)
Dinur, I.: The PCP theorem by gap amplification. J. ACM 54 (2007)
Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized approximation problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 121–129. Springer, Heidelberg (2006)
Escoffier, B., Paschos, V.T., Tourniaire, E.: Moderately exponential and parameterized approximation: some structural results (unpublished manuscript)
Fürer, M., Gaspers, S., Kasiviswanathan, S.P.: An exponential time 2-approximation algorithm for bandwidth. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 173–184. Springer, Heidelberg (2009)
Garey, M.R., Johnson, D.S.: Computers and intractability. In: A Guide to the Theory of NP-completeness, W. H. Freeman, San Francisco (1979)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. System Sci. 63, 512–530 (2001)
Kim, E.J., Williams, R.: Improved parameterized algorithms for above average constraint satisfaction. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 118–131. Springer, Heidelberg (2012)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. Assoc. Comput. Mach. 41, 960–981 (1994)
Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal 51, 60–78 (2008)
Mathieson, L.: A proof checking view of parameterized complexity. CoRR abs/1206.2436 (2012)
Moshkovitz, D., Raz, R.: Two query PCP with sub-constant error. In: Proc. FOCS 2008, pp. 314–323 (2008)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation and complexity classes. J. Comput. System Sci. 43, 425–440 (1991)
Vazirani, V.: Approximation algorithms. Springer, Berlin (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Bonnet, E., Escoffier, B., Kim, E.J., Paschos, V.T. (2013). On Subexponential and FPT-Time Inapproximability. In: Gutin, G., Szeider, S. (eds) Parameterized and Exact Computation. IPEC 2013. Lecture Notes in Computer Science, vol 8246. Springer, Cham. https://doi.org/10.1007/978-3-319-03898-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-03898-8_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03897-1
Online ISBN: 978-3-319-03898-8
eBook Packages: Computer ScienceComputer Science (R0)