# 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.

100 questions
Filter by
Sorted by
Tagged with
21 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 &...
18 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 ...
23 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 ...
59 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, ...
44 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 ...
82 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 ...
24 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 ...
30 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]$, ...
13 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? ...
42 views

193 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 ...
32 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 ...
38 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?
102 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 ...
52 views

521 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 ...
80 views

### Finding maximum weighted n disjoint cliques

Maximum weight clique problem has some attention but i could not find any efficient approaches to this problem yet. I acknowledge that it is np-hard, but are there any known approximations? Given a ...
I am very new to Graph Theory and I am trying to prove the following statement from a problem set for my class: Prove that if G is a regular graph on n vertices $(n \ge 2)$, then \$\omega(G) \in \{...