# Questions tagged [clique]

A clique is a subset of the vertices of a graph such that every pair of vertices in the subset is connected by an edge.

102 questions
Filter by
Sorted by
Tagged with
67 views

### Generating graphs with partially overlapping cliques

Currently, I am working on a research project where I will utilise reinforcement learning for the diversified top-$k$ clique search problem. To train the reinforcement learning algorithm, I need to ...
• 41
1 vote
30 views

### Cluster 3d points with constraints

I have some 3d point cloud I wish to cluster into some number of clusters. I have the probability of two points being in the same cluster given as some function of their relative locations, with the ...
• 193
1 vote
36 views

### Is the clique problem polynomial-time solvable still in unit disk graphs allowing different sized disks?

Clark et al. proved that the clique problem is polynomial-time solvable in unit disk graphs. Does anyone know if this result holds still if the disks are allowed to be different sizes? Or do such &...
• 582
1 vote
24 views

### Lower bound for worst case running time for k-clique problem

A naive algorithm for determining whether a graph with $|V|$ vertices has a clique of size $k$ is to list all $k$-subsets of $V$, and check each one to see whether it forms a clique. Why is the ...
• 13
1 vote
31 views

### Finding maximum clique given, for each edge, union of all cliques containing it

For every edge $e\in E$ of a graph $G=(V,E)$ we know the union $U_{e}$ of the edges of all cliques that contain $e$. Can we determine, in polynomial time, for a given edge $e_{0}\in E$, the size of ...
68 views

### Maximum number of cliques of size $\ge 2$ of a graph with exactly $m$ edges

Let $G=(V,E)$ be an undirected graph with $|E|=m$ edges. Given that any clique of size $\ge 2$ can be identified with its corresponding edges, and at most every subset $S\subseteq E$ creates a clique, ...
• 649
62 views

### Coming up with an adversary strategy for a clique of maximum size

I’m having trouble coming up with a good adversary strategy for this problem: Input: a graph G Output: the maximum size of any clique in G Where the algorithm asks each time, “are vertices x and y ...
• 31
455 views

### Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G. My algorithm is as follows: Generate all subgraphs of size k, and check ...
• 31
44 views

### Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, prove $L(M)=CLIQUE$

Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, when the sum of a clique is the sum of the weights on all of the edges. I ...
• 209
41 views

### Edge-disjoint clique cover

Informally, we want to partition the edges of a graph into a few cliques. Given $G=(V, E)$, we want to find subsets $V_1,\dots, V_k\subset V$ such that $E = E[V_1]\dot\cup \dots \dot\cup E[V_k]$, ...
1 vote
20 views

### $W$-hierarchy and parameterized search problems

I have two related questions: What are the ways to prove that a certain problem is in $W[t]$ in the W-hierarchy for parametrized complexity, except using the straight definition of boolean circuits? ...
46 views

• 13
1 vote
208 views

### Is this clique algorithm in polynomial time correct or might it have another time complexity?

I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity ...
1 vote
103 views

### Reduction for the proof that COMBI $:= \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$ is NP complete

Given the Language $COMBI := \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$. Proof that Combi is NP-complete. I tried to reduce Clique <=p Combi. I had two different ...
52 views

### Finding a clique in undirected graph is P or NP? (proof) [duplicate]

Finding a clique $C$ in an undirected graph $G= (V, E)$ such that $|C| > |V|/2$ is in P or NP-hard? How can I prove it?
• 101
165 views

### Find maximal clique consisting of at least half of the vertices

Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority ...
• 161
68 views

• 443
640 views

### Understanding CLIQUE structure

I am working on the following problem: Recall the definition of a complete graph Kn is a graph with n vertices such that every vertex is connected to every other vertex. Recall also that a clique is ...
• 225