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
4 votes
0 answers
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 ...
user avatar
  • 41
1 vote
0 answers
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 ...
user avatar
  • 193
1 vote
1 answer
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 &...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 13
1 vote
1 answer
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 ...
user avatar
4 votes
1 answer
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, ...
user avatar
  • 649
2 votes
1 answer
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 ...
user avatar
  • 31
0 votes
2 answers
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 ...
user avatar
  • 31
2 votes
1 answer
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 ...
user avatar
  • 209
0 votes
0 answers
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]$, ...
user avatar
1 vote
0 answers
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? ...
user avatar
-1 votes
1 answer
46 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} ...
user avatar
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 ...
user avatar
3 votes
1 answer
59 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 ...
user avatar
  • 649
5 votes
1 answer
60 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 ...
user avatar
  • 53
0 votes
1 answer
54 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. ...
user avatar
-1 votes
1 answer
82 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)...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
-3 votes
1 answer
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?
user avatar
  • 101
2 votes
2 answers
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 ...
user avatar
  • 161
0 votes
1 answer
68 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: \...
user avatar
  • 127
2 votes
1 answer
55 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 ...
user avatar
  • 128
3 votes
1 answer
76 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 ...
user avatar
  • 153
0 votes
1 answer
91 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 ...
user avatar
  • 87
1 vote
0 answers
31 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' \...
user avatar
0 votes
1 answer
355 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). ...
user avatar
  • 169
1 vote
2 answers
133 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. ...
user avatar
  • 21
2 votes
2 answers
568 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. ...
user avatar
  • 364
2 votes
2 answers
902 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 ...
user avatar
  • 21
2 votes
1 answer
78 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 ...
user avatar
  • 364
7 votes
1 answer
235 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 ...
user avatar
  • 1,425
2 votes
0 answers
42 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 ...
user avatar
3 votes
1 answer
1k 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 (...
user avatar
  • 75
2 votes
1 answer
35 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 ...
user avatar
0 votes
1 answer
585 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 ...
user avatar
3 votes
0 answers
710 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 ...
user avatar
  • 31
1 vote
1 answer
72 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 $...
user avatar
  • 11
2 votes
1 answer
78 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 ...
user avatar
  • 167
5 votes
1 answer
192 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\}$, ...
user avatar
1 vote
2 answers
199 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 ...
user avatar
4 votes
1 answer
151 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\...
user avatar
  • 41
1 vote
1 answer
924 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 ...
user avatar
0 votes
0 answers
95 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 ...
user avatar
  • 1
4 votes
1 answer
499 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 ...
user avatar
1 vote
0 answers
43 views

Best-known Boolean Circuits for Clique? [closed]

Not having received a satisfactory response to this question in math.SE, I am asking it here: In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-...
user avatar
  • 816
3 votes
1 answer
3k views

Given a set of intervals on the real line, find a minimum set of points that "cover" all the intervals

I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
user avatar
  • 151
2 votes
1 answer
73 views

Making a profit as a high-dimensional store owner?

Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient. Let's say that I am some business owner with a set of $...
user avatar
  • 443
2 votes
1 answer
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 ...
user avatar
  • 225
2 votes
0 answers
82 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 ...
user avatar
  • 21