# On the minimum edge cover and vertex partition by quasi-cliques problems

3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : A $\gamma$-quasi-clique in a simple undirected graph is a set of vertices which induces a subgraph with the edge density of at least $\gamma$ for $0<\gamma< 1$. A cover of a graph by $\gamma$-quasi-cliques is a set of $\gamma$-quasi-cliques where each edge of the graph is contained in at least one quasi-clique. The minimum cover by $\gamma$-quasi-cliques problem asks for a $\gamma$-quasi-clique cover with the minimum number of quasi-cliques. A partition of a graph by $\gamma$-quasi-cliques is a set of $\gamma$-quasi-cliques where each vertex of the graph belongs to exactly one quasi-clique. The minimum partition by $\gamma$-quasi-cliques problem asks for a vertex partition by $\gamma$-quasi-cliques with the minimum number of quasi-cliques. We show that the decision versions of the minimum cover and partition by $\gamma$-quasi-cliques problems are NP-complete for any fixed $\gamma$ satisfying $0<\gamma< 1$.
Document type :
Reports
Domain :

Cited literature [8 references]

https://hal.inria.fr/hal-00795429
Contributor : Equipe Roma <>
Submitted on : Tuesday, March 5, 2013 - 9:47:55 AM
Last modification on : Thursday, August 20, 2020 - 4:40:07 PM
Long-term archiving on: : Sunday, April 2, 2017 - 7:26:25 AM

### File

RR-8255.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00795429, version 2

### Citation

Oguz Kaya, Enver Kayaaslan, Bora Uçar. On the minimum edge cover and vertex partition by quasi-cliques problems. [Research Report] RR-8255, INRIA. 2013. ⟨hal-00795429v2⟩

Record views