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.
108
questions
0
votes
0
answers
41
views
Basic Clique Complexity Question
A question in a textbook says, suppose the regular Clique problem, which takes as input a graph G and a natural number k, and returns whether or not G has a clique of size >= k, can be decided in ...
2
votes
1
answer
48
views
Determining the minimum number of edges to add to a graph to obtain a clique of size $k$
As part of a hobby project I stubmled into the following question which has me stumped:
Given an undirected graph $G = (V, E)$ and an integer $k$, what is that smallest number of edges that need to be ...
0
votes
1
answer
28
views
Transforming a Travelling Salesman Problem to a Maximum Clique Problem
Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly ...
- 1
0
votes
0
answers
25
views
How to prove the performance ratio of the approximation algorithm of maximum clique is unbounded
Consider the following approximation algorithm for the problem of finding a maximum clique in a given graph $G$. Repeat the following step until the resulting graph is a clique. Delete from $G$ a ...
- 1
0
votes
1
answer
29
views
Is it correct to state the decision problem Clique can be solved in time $O(\min(n^kk^2, 2^{n/4}))$?
With the decision problem Clique, I mean:
Given a graph $G$, does $G$ admit a clique of size at least $k$?
From Wikipedia, one finds that the brute force algorithm of testing all possible subsets of ...
- 665
4
votes
0
answers
70
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
0
answers
33
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
1
answer
42
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 &...
- 665
1
vote
1
answer
32
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
1
answer
40
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 ...
user136613
4
votes
1
answer
75
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, ...
- 659
2
votes
1
answer
66
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 ...
user141218
0
votes
2
answers
916
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 ...
user141218
2
votes
1
answer
65
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 ...
- 223
0
votes
0
answers
48
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]$, ...
- 531
1
vote
0
answers
27
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? ...
- 49
-1
votes
1
answer
48
views
Are the following assertions true if P != NP?
We consider the NP-complete $CLIQUE$ problem. Let furthermore $MST^*$ be the minimum spanning tree problem. Assume that $P \ne NP$ and explain whether the following assertions hold:
$MST^* \le_{P} ...
2
votes
0
answers
59
views
A simple graph $G$ with even clique number, find a subset $A$ of the vertices, subgraph induced by $A,V-A$ have equal clique number
Given a simple graph $G=(V,E)$ s.t. $2\mid \omega(G)$,
Show that $\exists S\subseteq V\text{ s.t. } f_G(S)=f_G(V\setminus S)$
where $f_G(A)$ is the clique number of the sub-graph of $G$ induced by ...
- 21
3
votes
1
answer
76
views
Applications of the splittance of a graph/ Turning graphs into splitgraphs
Let $G=(V,E)$ be a graph. For $C\subseteq V$ let $G[C]$ be the subgraph of $G$ induced by $C$.
A split Graph is defined as follow:
$G$ is a split graph if there exists a subset $C\subseteq V$ so that ...
- 659
5
votes
1
answer
66
views
Maximum-weight set of cliques of size 3 with no common vertices in undirected graph
I'm looking for an algorithm/insight into a problem that's an extension of the Maximum Weight Matching problem. The maximum weight matching problem looks for the max-weight set of edges that contain 0 ...
- 53
0
votes
1
answer
59
views
Find a Cook Reduction from $R_{Clique}$ to its determinist problem
The question is to find Find a Cook Reduction from $R_{k-Clique}$ to its determinist problem.
Basically:
k-Clique: a group of $k$ nodes in the graph such there is an edge between every two nodes.
...
- 25
-1
votes
1
answer
92
views
Clique is NP hard to approximate up to $n^{a}$ for some $a \in (0,1)$
Given that
$\mathsf{NP}=\mathsf{PCP}_{[\frac{1}{n},1]}\left(O\left(\log n\right),\left(O(\log n\right)\right)$,
show that it is NP-hard to approximate clique up to factor of $n^a$ for some $a \in (0,1)...
- 13
1
vote
1
answer
221
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 ...
- 163
1
vote
1
answer
153
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 ...
- 163
-3
votes
1
answer
59
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
2
votes
2
answers
260
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
0
votes
1
answer
72
views
Reduce Clique to N-Degree-Clique
I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where:
$$ \text{N-Degree-Clique} = \{ \langle G, k\rangle: \...
- 127
2
votes
1
answer
64
views
Graph partition that maximize the number of triangles within its parts
Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal?
This ...
- 128
3
votes
1
answer
84
views
On Tarjan's paper "Finding a Maximum Clique"
In his paper, "Finding a Maximum Clique" from 1972 Robert Tarjan introduced an algorithm that finds maximum cliques in $O(1.286^n)$. You can find a link to his paper here.
In the second page ...
- 153
0
votes
1
answer
108
views
What is the complexity of k-clique problem with a predetermined vertex in the solution?
Clique (from WikiPedia):
Clique is a subset of vertices of an undirected graph such that every
two distinct vertices in the clique are adjacent; that is, its induced
subgraph is complete.
K-Clique ...
- 87
1
vote
0
answers
34
views
ILP relaxation for Cluster deletion on C5
I'm looking for additional constraints that get rid of fractional solutions for the LP relaxation of the Cluster Deletion problem:
Given an undirected graph $G = (V, E)$, find a min. sized $E' \...
- 135
0
votes
1
answer
427
views
Solving distance-d independent set in a simple way
I'm solving distance-d independent set problem, as a follow up to my last question. I'm not quite experienced in a subject, so I'm looking for a simple algorithm (which has to be an exact algorithm). ...
- 169
1
vote
2
answers
213
views
Is $\frac{n}{3}$-CLIQUE NP-complete?
Consider the problem
$\frac{n}{3}$-CLIQUE:
determining whether a graph contains a clique with at least $n/3$ vertices.
I want to prove it is NP-complete using a polynomial transformation from CLIQUE.
...
- 21
2
votes
2
answers
741
views
Max clique in interval graph
According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. ...
- 364
2
votes
2
answers
1k
views
Clique-problem for planar graph
I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion
This follows already from Kuratowski's theorem: a clique is at ...
- 21
2
votes
1
answer
82
views
Minimum unweighted anticlique (independent set) cover / partition
Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously ...
- 364
7
votes
1
answer
243
views
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph [closed]
So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices.
In general case, it is exponential.
I am trying to determine whether the ...
- 1,425
2
votes
0
answers
43
views
Question about the lower bound for $k \times k$-clique (under ETH) shown in "Slightly Superexponential Parameterized Problems"
I am reading the paper Slightly Superexponential Parameterized Problems at the moment and have two questions about it:
First question:
The paper gives a proof of the following statement
Theorem ...
- 179
4
votes
1
answer
2k
views
CLIQUE $\leq_p$ SAT
i'm trying to reduce CLIQUE to SAT:
Given: Graph G=(Vertices V, Edges E) and $k \in \mathbb{N}$
Output: Formular F such that if G contains a complete subgraph of size k, the formular is satisfiable (...
- 185
2
votes
1
answer
36
views
Algorithm to compute partitions of a graph in N cliques
does anyone know of an efficient algorithm to compute the partition of a graph in N cliques?
Notice that N is the number of the cliques and not the size of them.
I have heard of the 2 cliques ...
- 123
0
votes
1
answer
612
views
Online algorithm for finding of clique of size k
I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an ...
3
votes
0
answers
758
views
Minimum clique cover
How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time?
Having an undirected graph, I am trying to partition all its ...
- 31
1
vote
1
answer
75
views
Reducing CLIQUE to Super Connector problem
I am trying to show that our problem is NP-Complete by reducing the known problem CLIQUE to our problem.
Regular CLIQUE problem:
Input: An undirected graph $G$ and a positive integer $K$.
Goal: Does $...
- 11
2
votes
1
answer
80
views
Distributed MST Construction in O(log log n) Rounds in a Clique
I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5.
It shows by induction on k (phase number), that ...
- 167
5
votes
1
answer
198
views
Prove that "Finishing the degree in three years" problem is NP-Complete
I was asked in an interview the following question:
We'll define the "Finishing the degree in three years" problem in the following manner:
Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, ...
- 69
1
vote
2
answers
236
views
Maximal cliques in a multipartite graph - efficient?
I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class.
Now I am looking for the optimal subset such that each of the N classes is represented exactly ...
- 11
4
votes
1
answer
174
views
Does the intersection of VC and CLIQUE belong to NPC?
Define: $$L=\{(G,k) : G\text{ has a vertex cover of size at most $k$, and a clique of size at least $k$}\}$$
I need to determine whether $L\in \mathrm{NPC}$ or $L\in \mathrm{P}$. I suspect that $L\...
- 41
1
vote
1
answer
1k
views
Generalization of Subgraph Isomorphism
I am wondering how to prove that Subgraph Isomorphism is NP Complete. Wikipedia indicates that the CLIQUE problem can be used to demonstrate this, but I can't figure out how. I also found this link ...
- 146
0
votes
0
answers
114
views
Clique number of a graph given its order and average degree
Let $G$ be simple graph of order $N$, and let $\bar{d}$ be its average degree.
Find the maximum value of $\omega(G)$ (the clique number of $G$) as a function of $N$ and $\bar{d}$.
Find the ...
- 1
4
votes
1
answer
609
views
Why is EXACT-CLIQUE not in co-NP?
In my lecture I saw the problem of
$\text{EXACT-CLIQUE} = \{\langle G,k\rangle : \text{the largest clique in $G$ is of order $k$}\}$
I understand this problem is obviously not in NP as we would need ...
- 115