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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
99 views

Prove "Vertex Cover OR Clique" is NP complete

Instance: An undirected graph $G$ and a positive integer $k$ Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$? Obviously, this problem is solved by polynomial ...
Hugh Mann's user avatar
3 votes
0 answers
74 views

Minimum number of edges required to limit the size of the independent set

Consider the following problem: For $k \le n$, what is the smallest number of edges in the graph with $n$ vertices so that the maximum independent set has size at most $k$? I.e., given an empty ...
Dmitry's user avatar
  • 345
0 votes
1 answer
100 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 ...
emily-cs's user avatar
0 votes
1 answer
107 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-...
user's user avatar
  • 1
0 votes
0 answers
19 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 ...
pyridoxal_trigeminus's user avatar
0 votes
0 answers
34 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 ...
Yavuz Bozkurt's user avatar
0 votes
0 answers
23 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,...
JustBlaze's user avatar
2 votes
1 answer
225 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 ...
Lonatico's user avatar
  • 121
1 vote
3 answers
50 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 ...
PatrickBateman's user avatar
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) + \...
guinny's user avatar
  • 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, ...
Manel Rosana's user avatar
-1 votes
1 answer
31 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 ...
GuestPersonOnThisShow's user avatar
2 votes
1 answer
101 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 ...
Lilith's user avatar
  • 23
0 votes
0 answers
48 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 ...
Abhishek Manikandan's user avatar
2 votes
1 answer
131 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 ...
CutOnBumInBand's user avatar
0 votes
1 answer
91 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 ...
Emily's user avatar
  • 1
0 votes
0 answers
121 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 ...
RJ94's user avatar
  • 1
0 votes
1 answer
43 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 ...
J. Schmidt's user avatar
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 ...
Jesse's user avatar
  • 41
1 vote
0 answers
40 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 ...
Gulzar's user avatar
  • 193
1 vote
1 answer
51 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 &...
J. Schmidt's user avatar
1 vote
1 answer
57 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 ...
XYZ's user avatar
  • 13
1 vote
1 answer
41 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 ...
user avatar
4 votes
1 answer
100 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, ...
Sudix's user avatar
  • 709
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 ...
user avatar
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 ...
user avatar
2 votes
1 answer
90 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 ...
vesii's user avatar
  • 223
0 votes
0 answers
63 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]$, ...
Ameer Jewdaki's user avatar
1 vote
0 answers
36 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? ...
Ofir Gordon's user avatar
-1 votes
1 answer
50 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} ...
pekusbill's user avatar
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 ...
hehelego's user avatar
3 votes
1 answer
113 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 ...
Sudix's user avatar
  • 709
5 votes
1 answer
128 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 ...
TLF's user avatar
  • 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. ...
Iam Spano's user avatar
-1 votes
1 answer
113 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)...
hash man's user avatar
1 vote
1 answer
245 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 ...
OuttaSpaceTime's user avatar
1 vote
1 answer
277 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 ...
OuttaSpaceTime's user avatar
-3 votes
1 answer
83 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?
Lee Yaan's user avatar
  • 101
2 votes
2 answers
312 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 ...
mgus's user avatar
  • 161
0 votes
1 answer
155 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: \...
Yuki1112's user avatar
  • 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 ...
JEK's user avatar
  • 128
3 votes
1 answer
97 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 ...
Travis's user avatar
  • 153
0 votes
1 answer
164 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 ...
Mamun's user avatar
  • 87
1 vote
0 answers
39 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' \...
eager2learn's user avatar
0 votes
1 answer
513 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). ...
qalis's user avatar
  • 169
1 vote
2 answers
445 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. ...
yubgf's user avatar
  • 21
2 votes
2 answers
1k 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. ...
taktoa's user avatar
  • 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 ...
Vakole's user avatar
  • 21
2 votes
1 answer
88 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 ...
taktoa's user avatar
  • 364
7 votes
1 answer
252 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 ...
padawan's user avatar
  • 1,435