Skip to Main content Skip to Navigation
Reports

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

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$.
Complete list of metadata

https://hal.inria.fr/hal-00795429
Contributor : Equipe Roma <>
Submitted on : Thursday, February 28, 2013 - 10:30:32 AM
Last modification on : Thursday, August 20, 2020 - 4:40:07 PM
Long-term archiving on: : Sunday, April 2, 2017 - 6:42:16 AM

File

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

Identifiers

  • HAL Id : hal-00795429, version 1

Collections

Citation

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

Share

Metrics

Record views

56

Files downloads

270