# Questions tagged [clique]

The tag has no usage guidance.

65 questions
Filter by
Sorted by
Tagged with
126 views

### Maximum cliques of the transitive closure of a chordal DAG

Let $G=(V,A)$ be a directed acyclic graph, for which the underlying undirected graph is chordal (so that every induced cycle in the underlying undirected graph is a triangle). It is known that in a ...
109 views

160 views

250 views

### Hardness of $k$-Plex

Definition. Given an undirected graph $G = (V,E)$, a $k$-plex is a subgraph $G'$ of $G$ such that each vertex in $G'$ is connected to at least $s - k$ other vertices in $G'$, where $s$ is the # of ...
624 views

### Finding All Cliques of an Undirected Graph

How can I list all cliques of an Undirected Graph ? (Not all maximal cliques, like the Bron-Kerbosch algorithm)
278 views

1k views

### Algorithms for online clique detection

Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?
177 views

### Minimum Clique edge cover to cilque vertex cover

Suppose, there is an algorithm for enumerating minimum clique edge cover. Is it always possible to convert the algorithm to enumerate clique vertex cover ?
194 views

191 views

### Finding assignment-minimum complete k-partite graph cover

Is there any work on approximation algorithms (or exact algorithms) for finding an assignment-minimum cover of an arbitrary graph using complete k-partite subgraphs? I'm assuming this problem is NP-...
1k views

### Hardest problems to approximate

Under some assumptions, it is hard to approximate MAX-CLIQUE within a factor $n^{1-\epsilon}$ for any $\epsilon >0$. Are there any other problems that are known to be equally hard to approximate? I'...
144 views

### Help with the definition of clique percolation

So I can find the Wiki article okay, as I think I understand that this is a definition of a special community in a graph. However their image in Fig. 1 confuses me from the description. As I ...
### Finding minimum weight $k$ cliques in a complete graph
For an undirected weighted complete graph $G = (V, E)$. Assuming the edge weight indicates the similarity between different nodes, the smaller $w_{ij}$ is, it means $i$ and $j$ are more similar ...