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.
120
questions
-1
votes
0
answers
14
views
Clique to SAT example explanation
We are at college trying to implement the reduction of the clique problem to a SAT problem but I dont quite get the examples of the slides if someone can give me a not so technical explanation of what'...
0
votes
1
answer
44
views
Constructing an SAT formula from a Clique graph
We were given this practice question to do in a lecture and its solution afterwards. I have spent hours upon hours trying to understand the solution but still do not understand.
From my knowledge when ...
- 1
0
votes
1
answer
52
views
3sat to clique reduction program
I am searching for a program to convert 3sat to clique problem.
I tried following links
https://www.geeksforgeeks.org/maximal-clique-problem-recursive-solution/
https://www.geeksforgeeks.org/find-all-...
- 1
0
votes
0
answers
15
views
Current best output-sensitive algorithm for computing all maximal cliques of a graph
I am looking for a reference on the most optimal output-sensitive algorithm currently available for listing all maximal cliques in a graph.
I know the Bron-Kerbosch algorithm is highly utilized, but ...
0
votes
0
answers
25
views
How to prove Set-Cover problem is NP hard via reduction from Clique problem?
Since I know that the reduction Clique $\leq_{p}$ Vertex-Cover and Vertex-Cover $\leq_{p}$ Set-Cover are possible, I know how to show this using transitivity property of reductions. However is there ...
0
votes
0
answers
22
views
Maximum Subset Sum with Pairwise Constraints
(Note: I am posting after reading some possibly related posts because I could not find a fitting solution.)
Given some finite set of nodes $S$, where each node $s_i \in S$ has a value $val(s_i) \in [0,...
- 11
2
votes
1
answer
128
views
Fast $k$-clique checking algorithm?
I have a problem where part of it requires answering the question: does graph $G=(V,E)$ contain a clique of size at least $k$?
Obviously, answering this question is a NP-Complete problem. I am no ...
- 121
1
vote
3
answers
47
views
Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?
Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?
Is it correct to say that it doesn't exist because clique is ...
0
votes
0
answers
25
views
Find maximum sum of K elements in a graph with unary and binary terms
I have an algorithmic problem that I managed to reduce to the following form:
Given a graph with $N$ elements, select exactly $K$ elements to maximize the following:
$$
\max \Sigma_{k \in K} V(S_k) + \...
- 1
4
votes
0
answers
74
views
Constant factor approximation algorithm for Vertex Deletion version of Maximum Diameter Bounded Subgraph
I've been stuck with this problem for quite a while now, and after reading so many papers I'm unsure whether this is even possible.
The problem is quite simple:
Given $G = (V, E)$ an undirected graph, ...
- 41
-1
votes
1
answer
29
views
Half Clique Property question
Hey I had this question and am stuck on part (b).
I don't see how its possible to find a graph with 7 vertices and 15 edges that does not have the half-clique problem. If there is a way, could someone ...
2
votes
1
answer
81
views
Is the clique decision problem in co-NP?
Is the clique decision problem in co-NP?
Definitions:
"In the clique decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph ...
- 23
0
votes
0
answers
45
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
80
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
64
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
97
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
37
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 ...
- 737
4
votes
0
answers
71
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
37
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
48
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 &...
- 737
1
vote
1
answer
52
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
85
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
72
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
1k
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
86
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
59
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
34
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
49
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
61
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
100
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
103
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
61
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
105
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
239
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
217
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
68
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
300
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
95
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
67
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
95
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
143
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
37
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
492
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
362
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
971
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
86
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
248
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
48
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