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

Cited literature [8 references]  Display  Hide  Download

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

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, INRIA. 2013. ⟨hal-00795429v2⟩

Share

Metrics

Record views

570

Files downloads

1978