N. Faisal and . Abu-khzam, Kernelization algorithms for d-hitting set problems, LNCS, vol.4619, pp.434-445, 2007.

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM, vol.45, issue.3, pp.501-555, 1998.
DOI : 10.1145/278298.278306

V. Bafna, P. Berman, and T. Fujito, A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem, SIAM Journal on Discrete Mathematics, vol.12, issue.3, pp.289-297, 1999.
DOI : 10.1137/S0895480196305124

L. Hans and . Bodlaender, A cubic kernel for feedback vertex set, STACS, pp.320-331, 2007.

L. Hans, R. G. Bodlaender, M. R. Downey, D. Fellows, and . Hermelin, On problems without polynomial kernels (extended abstract), LNCS, vol.5125, issue.1, pp.563-574, 2008.

L. Cai and J. Chen, On Fixed-Parameter Tractability and Approximability of NP Optimization Problems, Journal of Computer and System Sciences, vol.54, issue.3, pp.465-474, 1997.
DOI : 10.1006/jcss.1997.1490

L. Cai and X. Huang, Fixed-Parameter Approximation: Conceptual Framework and Approximability Results, Lecture Notes in Computer Science, vol.4169, pp.96-108, 2006.
DOI : 10.1007/11847250_9
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.219.2987

J. Chen, I. A. Kanj, and W. Jia, Vertex Cover: Further Observations and Further Improvements, Journal of Algorithms, vol.41, issue.2, pp.280-301, 2001.
DOI : 10.1006/jagm.2001.1186
URL : http://anyserver.cityu.edu.hk/weijia/publication/vertex_cover.pdf

P. Erd?, O. , and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc, vol.35, pp.85-90, 1960.

R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation of SIAM-AMS Proceedings, pp.43-73, 1974.

U. Feige, M. Hajiaghayi, and J. R. Lee, Improved Approximation Algorithms for Minimum Weight Vertex Separators, SIAM Journal on Computing, vol.38, issue.2, pp.629-657, 2008.
DOI : 10.1137/05064299X
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.597.5634

J. Flum and M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), 2006.

L. Fortnow and R. Santhanam, Infeasibility of instance compression and succinct PCPs for NP, Proceedings of the fourtieth annual ACM symposium on Theory of computing, STOC 08, pp.133-142, 2008.
DOI : 10.1145/1374376.1374398

E. Halperin, Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs, SIAM Journal on Computing, vol.31, issue.5, pp.1608-1623, 2002.
DOI : 10.1137/S0097539700381097

S. Khanna, R. Motwani, M. Sudan, and U. V. Vazirani, On Syntactic versus Computational Views of Approximability, SIAM Journal on Computing, vol.28, issue.1, pp.164-191, 1998.
DOI : 10.1137/S0097539795286612

G. Phokion, M. N. Kolaitis, and . Thakur, Logical definability of NP optimization problems, Inf. Comput, vol.115, issue.2, pp.321-353, 1994.

G. Phokion, M. N. Kolaitis, and . Thakur, Approximation properties of NP minimization classes, J. Comput. Syst. Sci, vol.50, issue.3, pp.391-411, 1995.

A. Natanzon, R. Shamir, and R. Sharan, A Polynomial Approximation Algorithm for the Minimum Fill-In Problem, SIAM Journal on Computing, vol.30, issue.4, pp.1067-1079, 2000.
DOI : 10.1137/S0097539798336073

R. Niedermeier, Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications), 2006.

N. Nishimura, P. Ragde, and D. M. Thilikos, Smaller Kernels for Hitting Set Problems of Constant Arity, LNCS, vol.3162, pp.121-126, 2004.
DOI : 10.1007/978-3-540-28639-4_11

C. H. Papadimitriou, Computational Complexity, 1993.

H. Christos, Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes, J. Comput. Syst. Sci, vol.43, issue.3, pp.425-440, 1991.