HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, March 5, 2013 - 9:47:55 AM
Last modification on : Monday, May 16, 2022 - 4:46:02 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⟩

Share

Metrics

Record views

326

Files downloads

819