?. V. Which, Thus, the approximation ratio of Algorithm 7 is 1 /3, since optimal densest k-subgraphs are built for G[V 1 ], G[V 2 ] and B, and one of them contains at least one third of the optimum number of edges In Line 1, a minimum vertex cover can be computed in O * (1.2738 ? ) as in [18]. As |V 1 and V \ V * is an independent set. Finally, as B is a bipartite graph, Proof. By construction E = E(V 1 ) ? E(V 2 ) ? E Line 3 runs in O * Line 4, use Generic since |V 2 ? V * | = ? Line 5 runs in O * (2 min{|V 1 |,|V 2 } ) = O * (2 |V 1 | ) = O *

]. R. References1, K. Andersen, and . Chellapilla, Finding dense subgraphs with size bounds, WAW'09, pp.25-36, 2009.

S. Arora, D. R. Karger, and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems, Journal of Computer and System Sciences, vol.58, issue.1, pp.193-210, 1999.
DOI : 10.1006/jcss.1998.1605

Y. Asahiro, R. Hassin, and K. Iwama, Complexity of finding dense subgraphs, Discrete Applied Mathematics, vol.121, issue.1-3, pp.15-26, 2002.
DOI : 10.1016/S0166-218X(01)00243-8
URL : http://doi.org/10.1016/s0166-218x(01)00243-8

J. Backer and J. M. , Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs, Information Processing Letters, vol.110, issue.16, pp.635-638, 2010.
DOI : 10.1016/j.ipl.2010.05.011

A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and A. Vijayaraghavan, Detecting high log-densities, Proceedings of the 42nd ACM symposium on Theory of computing, STOC '10, pp.201-210, 2010.
DOI : 10.1145/1806689.1806719

A. Billionnet and F. Roupin, A deterministic approximation algorithm for the densest k-subgraph problem, International Journal of Operational Research, vol.3, pp.301-314, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00596169

A. Björklund, T. Husfeldt, and M. Koivisto, Set Partitioning via Inclusion-Exclusion, SIAM Journal on Computing, vol.39, issue.2, pp.546-563, 2009.
DOI : 10.1137/070683933

N. Bourgeois, F. Della-croce, B. Escoffier, V. Th, and . Paschos, Fast algorithms for min independent dominating set, Discrete Applied Mathematics, vol.161, issue.4-5, pp.4-5558, 2013.
DOI : 10.1016/j.dam.2012.01.003
URL : https://hal.archives-ouvertes.fr/hal-01508849

N. Bourgeois, B. Escoffier, V. Th, and . Paschos, Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Discrete Applied Mathematics, vol.159, issue.17, pp.1954-1970, 2011.
DOI : 10.1016/j.dam.2011.07.009
URL : http://doi.org/10.1016/j.dam.2011.07.009

N. Bourgeois, B. Escoffier, V. Th, J. M. Paschos, and . Van-rooij, Fast Algorithms for max independent set, Algorithmica, vol.7, issue.3, pp.382-415, 2012.
DOI : 10.1007/s00453-010-9460-7
URL : https://hal.archives-ouvertes.fr/hal-00880187

N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V. Th et al., The max quasi-independent set problem, Journal of Combinatorial Optimization, vol.20, issue.2, pp.94-117, 2012.
DOI : 10.1007/s10878-010-9343-5
URL : https://hal.archives-ouvertes.fr/hal-00880207

N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V. Th et al., Exact and Approximation Algorithms for Densest k-Subgraph, WALCOM'13, pp.114-125, 2013.
DOI : 10.1007/978-3-642-36065-7_12
URL : https://hal.archives-ouvertes.fr/hal-01215976

L. Brankovic and H. Fernau, Combining Two Worlds: Parameterised Approximation for Vertex Cover, ISAAC'10, pp.390-402, 2010.
DOI : 10.1007/978-3-642-17517-6_35

R. L. Brooks, On colouring the nodes of a network, Mathematical Proceedings of the Cambridge Philosophical Society, vol.37, issue.02, pp.194-197, 1941.
DOI : 10.1017/S030500410002168X

L. Cai, Parameterized Complexity of Cardinality Constrained Optimization Problems, The Computer Journal, vol.51, issue.1, pp.102-121, 2007.
DOI : 10.1093/comjnl/bxm086
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.7121

L. Cai and X. Huang, Fixed-parameter approximation: conceptual framework and approximability results, IWPEC'06, pp.96-108, 2006.
DOI : 10.1007/11847250_9
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.219.2987

M. Chang, L. Chen, L. Hung, P. Rossmanith, and G. Wu, Exact algorithms for problems related to the densest k-set problem, Information Processing Letters, vol.114, issue.9, pp.510-513, 2014.
DOI : 10.1016/j.ipl.2014.04.009

J. Chen, I. A. Kanj, and G. Xia, Improved upper bounds for vertex cover, Theoretical Computer Science, vol.411, issue.40-42, pp.3736-3756, 2010.
DOI : 10.1016/j.tcs.2010.06.026
URL : http://doi.org/10.1016/j.tcs.2010.06.026

D. G. Corneil and Y. Perl, Clustering and domination in perfect graphs, Discrete Applied Mathematics, vol.9, issue.1, pp.27-39, 1984.
DOI : 10.1016/0166-218X(84)90088-X
URL : http://doi.org/10.1016/0166-218x(84)90088-x

M. Cygan, L. Kowalik, and M. Wykurz, Exponential-time approximation of weighted set cover, Information Processing Letters, vol.109, issue.16, pp.957-961, 2009.
DOI : 10.1016/j.ipl.2009.05.003
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.534.2721

M. Cygan and M. Pilipczuk, Exact and approximate bandwidth, Theoretical Computer Science, vol.411, pp.40-423701, 2010.
DOI : 10.1016/j.tcs.2010.06.018
URL : http://doi.org/10.1016/j.tcs.2010.06.018

R. G. Downey and M. R. Fellows, Parameterized complexity. Monographs in Computer Science, 1999.

R. G. Downey, M. R. Fellows, and C. Mccartin, Parameterized Approximation Problems, IWPEC'06, pp.121-129, 2006.
DOI : 10.1007/11847250_11
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.467.9346

U. Feige, G. Kortsarz, and D. Peleg, The Dense k -Subgraph Problem, Algorithmica, vol.29, issue.3, pp.410-421, 2001.
DOI : 10.1007/s004530010050

U. Feige and M. Langberg, Approximation Algorithms for Maximization Problems Arising in Graph Partitioning, Journal of Algorithms, vol.41, issue.2, pp.174-211, 2001.
DOI : 10.1006/jagm.2001.1183
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.1611

U. Feige and M. Seltser, On the densest k-subgraph problem, 1997.

F. V. Fomin, F. Grandoni, and D. Kratsch, A measure & conquer approach for the analysis of exact algorithms, Journal of the ACM, vol.56, issue.5, 2009.
DOI : 10.1145/1552285.1552286

F. V. Fomin and K. Høie, Pathwidth of cubic graphs and exact algorithms, Information Processing Letters, vol.97, issue.5, pp.191-196, 2006.
DOI : 10.1016/j.ipl.2005.10.012
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.3486

G. Gallo, P. L. Hammer, and B. Simeone, Quadratic knapsack problems, Mathematical Programming, vol.12, pp.132-149, 1980.
DOI : 10.1007/BFb0120892

A. Goldberg, Finding a maximum density subgraph, 1984.

G. Jäger and A. Srivastav, Improved Approximation Algorithms for Maximum Graph Partitioning Problems, Journal of Combinatorial Optimization, vol.90, issue.1, pp.133-167, 2005.
DOI : 10.1007/s10878-005-2269-7

R. M. Karp, Reducibility among combinatorial problems, Complexity of computer computations, pp.85-103, 1972.
DOI : 10.1007/978-3-540-68279-0_8

S. Khot, Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique, 45th Annual IEEE Symposium on Foundations of Computer Science, pp.136-145, 2004.
DOI : 10.1109/FOCS.2004.59

S. Khuller and B. Saha, On Finding Dense Subgraphs, ICALP'09, pp.597-608, 2009.
DOI : 10.1007/978-3-642-02927-1_50
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.157.704

C. Komusiewicz and M. Sorge, An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems, Discrete Applied Mathematics, vol.193, pp.145-161, 2015.
DOI : 10.1016/j.dam.2015.04.029

M. Liazi, I. Milis, and V. Zissimopoulos, A constant approximation algorithm for the densest k-subgraph problem on chordal graphs, Information Processing Letters, vol.108, issue.1, pp.29-32, 2008.
DOI : 10.1016/j.ipl.2008.03.016

D. Marx, Parameterized Complexity and Approximation Algorithms, The Computer Journal, vol.51, issue.1, pp.60-78, 2008.
DOI : 10.1093/comjnl/bxm048
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.728

H. Moser, Exact algorithms for generalizations of vertex cover, 2005.

T. Nonner, PTAS for Densest $$k$$ k -Subgraph in Interval Graphs, Algorithmica, vol.45, issue.5, pp.528-539, 2016.
DOI : 10.1007/s00453-014-9956-7
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.370.910

U. Pferschy and J. Schauer, Approximation of the Quadratic Knapsack Problem, INFORMS Journal on Computing, vol.28, issue.2, pp.308-318, 2016.
DOI : 10.1287/ijoc.2015.0678

D. J. Rader-jr and G. J. Woeginger, The quadratic 0???1 knapsack problem with series???parallel support, Operations Research Letters, vol.30, issue.3, pp.159-166, 2002.
DOI : 10.1016/S0167-6377(02)00122-0

B. Reed, Paths, Stars and the Number Three, Combinatorics, Probability and Computing, vol.17, issue.03, pp.277-295, 1996.
DOI : 10.1002/net.3230070305

R. Taylor, Approximation of the Quadratic Knapsack Problem, Operations Research Letters, vol.44, issue.4, pp.495-497, 2016.
DOI : 10.1016/j.orl.2016.05.005

J. M. Van-rooij, J. Nederlof, and T. C. Van-dijk, Inclusion/Exclusion Meets Measure and Conquer, ESA'09, pp.554-565, 2009.
DOI : 10.1007/978-3-642-04128-0_50