# Exact and superpolynomial approximation algorithms for the densest $k$-subgraph problem

3 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : The densest $k$-subgraph problem is a generalization of the maximum clique problem, in which we are given a graph and a positive integer k, and we search among all the subsets of k vertices of the input graph for the subset which induces the maximum number of edges. densest $k$-subgraph is a well known optimization problem with various applications as, for example, in the design of public encryption schemes, the evaluation of certain financial derivatives, the identification of communities with similar characteristics, etc. In this paper, we first present algorithms for finding exact solutions for densest $k$-subgraph which improve upon the standard exponential time complexity of an exhaustive enumeration by creating a link between the computation of an optimum for this problem to the computation of other graph-parameters such as dominating set, vertex cover, longest path, etc. An FPT algorithm is also proposed which considers as a parameter the size of the minimum vertex cover. Finally, we present several approximation algorithms which run in moderately exponential or parameterized time, describing trade-offs between complexity and approximability. In contrast with most of the algorithms in the bibliography, our algorithms need only polynomial space.
Keywords :
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2017, 262, pp.894 - 903. 〈10.1016/j.ejor.2017.04.034〉
Domaine :

Littérature citée [45 références]

https://hal.inria.fr/hal-01539561
Contributeur : Lucarelli Giorgio <>
Soumis le : jeudi 15 juin 2017 - 09:50:53
Dernière modification le : jeudi 11 octobre 2018 - 08:48:05
Document(s) archivé(s) le : mardi 12 décembre 2017 - 13:03:38

### Fichier

k-densest.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th Paschos. Exact and superpolynomial approximation algorithms for the densest $k$-subgraph problem. European Journal of Operational Research, Elsevier, 2017, 262, pp.894 - 903. 〈10.1016/j.ejor.2017.04.034〉. 〈hal-01539561〉

### Métriques

Consultations de la notice

## 387

Téléchargements de fichiers