Questions tagged [clique]
The clique tag has no usage guidance.
68
questions
21
votes
5
answers
3k
views
Reasons for which a graph may be not $k$ colorable?
While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to ...
- 6,615
17
votes
2
answers
699
views
Hardness of parameterized CLIQUE?
Let $0\le p\le 1$ and consider the decision problem
CLIQUE$_p$
Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges
Question: does $G$ contain a clique on at ...
- 18.7k
17
votes
0
answers
571
views
Linear-time algorithm to test if clique number equals degeneracy bound?
Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique.
A well-known bound on the clique number is $\omega\le d+1$, which is ...
- 1,156
15
votes
2
answers
1k
views
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
The $k$-cycle problem is as follows:
Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges.
Question: Does there exist a (proper) $k$-cycle in $G$?
Background: For any ...
- 4,900
15
votes
1
answer
244
views
2FA state complexity of k-Clique?
In simple form:
Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states?
Details
Of interest here are $v$-vertex graphs encoded using a sequence of ...
- 18.7k
14
votes
0
answers
650
views
Does solving matrix multiplication in quadratic time imply that SETH is false?
I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time.
In other words, ...
- 4,900
13
votes
1
answer
619
views
Is counting maximal cliques in an incomparability graph #P-complete?
This question is motivated by a MathOverflow question by Peng Zhang. Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs (...
- 7,083
13
votes
1
answer
2k
views
Improving Cook's generic reduction for Clique to SAT?
I am interested in reducing $k$-Clique to SAT without making the instance much larger.
Clique is in NP so it can be reduced to SAT using logarithmic space.
The straightforward Garey/Johnson textbook ...
- 18.7k
12
votes
4
answers
4k
views
The number of cliques in a graph: the Moon and Moser 1965 result
I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't ...
11
votes
1
answer
1k
views
3-Clique Partition for graphs of fixed diameter
The 3-Clique Partition problem is the problem of determining whether the vertices of a graph, say $G$, can be partitioned into 3 cliques. This problem is NP-hard by a simple reduction from the 3-...
- 741
10
votes
1
answer
847
views
Complexity of k-clique for hypergraphs
Classic Problem:
Let a number $k$ be given. The $k$-clique problem is as follows.
Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent?
...
- 4,900
10
votes
1
answer
237
views
Computing the union closure
Given a family $\mathcal F$ of at most $n$ subsets of $\{ 1, 2, \dots, n \}$.
The union closure $\mathcal F$ is another set family $\mathcal C$ containing every set that can be constructed by taking ...
- 1,319
9
votes
2
answers
758
views
Clique Enumeration Algorithm
I am reading an old paper of M.C. Golumbic about EPT (edge intersection of paths in a tree) graphs. In the paper it is shown that the number of maximal cliques of an EPT graph instance is polynomial. ...
- 934
9
votes
0
answers
252
views
A reduction between small cliques problems
I'm looking for a reduction that gets a graph $G=(V_G,E_G)$ and outputs a graph $H$ that satisfies the following requirements.
If $G$ contains a triangle, then $H$ contains a clique of size 9.
If $G$ ...
- 1,897
8
votes
1
answer
743
views
Max-clique in line graph of hypergraph
Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph ...
- 1,100
8
votes
1
answer
508
views
Algorithms and computational complexity of clique and biclique covers
I've been reading a paper by a mathematical chemist. He proposes some indices to measure the complexity of molecules. From here on in, instead of molecules, think undirected connected graphs: a ...
- 6,954
7
votes
4
answers
1k
views
Hardest problems to approximate
Under some assumptions, it is hard to approximate MAX-CLIQUE within a factor $n^{1-\epsilon}$ for any $\epsilon >0$. Are there any other problems that are known to be equally hard to approximate? I'...
- 1,156
7
votes
3
answers
505
views
Graph classes in which CLIQUE is known to be NP-hard?
Given a graph $G$ and a positive integer $k$, the CLIQUE problem asks if $G$ contains a clique (complete subgraph) on at least $k$ vertices. This problem is long known to be NP-complete --- in fact, ...
- 1,384
7
votes
1
answer
959
views
On reducing the hardness of CNF-SAT to k-Clique
CNF-SAT refers to the following problem:
Given a boolean formula $\phi$ in conjunctive normal form, does there
exist an assignment to the variables that satisfies $\phi$.
There are several ...
- 4,900
7
votes
1
answer
258
views
Tree-decomposition with clique interfaces
Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:
For every edge $\{v_1,v_2\} \in E$, there ...
- 1,177
7
votes
2
answers
330
views
Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$
I am trying to find results on the best known time complexity for finding $(1+\epsilon) \log n$ sized cliques in $G(n,1/2)$. More general results would be great, i.e. if $C_p$ is the constant such ...
- 203
7
votes
1
answer
643
views
Minimal polynomial reduction of dominating set to max clique
Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a dominating set of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$
It is well known that it is NP ...
- 641
7
votes
1
answer
291
views
Erdos conjecture, number of cliques, Turan`s graph
Erdos&Stone conjectured in 1946-08 that
there are at least $ck-1$ (k+1)-cliques in $G=(V,E)$
whenever $|V|=ck$, $|E|-1$ is the edge-count in Turan's
$T(|V|,k)$, i.e.,
$|E|= 1+\lfloor {(k-1)|...
- 171
7
votes
0
answers
97
views
Complexity of computing the simplicial width of a graph
Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:
For every edge $\{v_1,v_2\} \in E$, there ...
- 1,177
6
votes
0
answers
176
views
Statistical Algorithms vs Convex Relaxations - Planted Clique
I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ?
A recent paper by Feldman, ...
- 656
5
votes
2
answers
302
views
Hardness of $k$-Plex
Definition. Given an undirected graph $G = (V,E)$, a $k$-plex is a subgraph $G'$ of $G$ such that each vertex in $G'$ is connected to at least $s - k$ other vertices in $G'$, where $s$ is the # of ...
user22369
5
votes
1
answer
464
views
Worst case ratio between minimum clique cover and maximum independent set
The maximum independent set problem gives a lower bound for the minimum clique cover problem. This is easy to see because given any clique cover together with an independent set, any two vertices ...
- 916
5
votes
2
answers
1k
views
Algorithms for online clique detection
Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?
- 53
5
votes
1
answer
422
views
On Zero sum perfect matching
Fix $c\geq1$.
Input is a $m$ vertex complete graph with edges assigned $a_1,\dots,a_{\frac{m(m-1)}2}\in\Bbb Z$ in some order.
Is it $\mathsf{NP}$-complete to decide if there is a perfect matching of ...
user34945
5
votes
1
answer
394
views
Counting the number of K4
I was going over this paper and I don't understand a certain proof (section five phase 2).
Given a graph G=(V,E) partitioned into the sets of vertices L and H. The vertices in L are at most D where D ...
- 53
4
votes
3
answers
3k
views
Maximum-clique practical applications
The question is: what are examples of clique problem applications? I mean, what problems can be solved by reducing to clique problem (sorry for tautology)?
All I came with is finding social cliques: ...
- 41
4
votes
3
answers
743
views
M-clique covers in complete graphs
Let us consider a complete weighted graph, with $NM$ nodes.
Our objective is to find, among all possible combinations of $N$ disjoint $M$-cliques (each clique consisting of $M$ nodes), the ...
- 43
4
votes
1
answer
205
views
Polynomial-time distinguishability threshold of planted clique
I have a basic question regarding the best known polynomial-time "distinguishing advantage" for the planted clique problem. By this, I'm referring to the problem of distinguishing the distribution $G(...
- 551
3
votes
4
answers
3k
views
Finding cliques in a big graph
I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques ...
- 595
3
votes
1
answer
130
views
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
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 ...
- 93
3
votes
2
answers
3k
views
Clique graph of bipartite graphs
The clique graph $C$ of a given graph $G$ has the maximal cliques of $G$ as vertices and their is an edge between two vertices in $C$ iff the corresponding cliques share some vertices.
Now for ...
- 1,006
3
votes
1
answer
124
views
Minimal clique edge cover vs minimalist (assignment-minimum) ones
Given a graph $G=(V,E)$, a clique edge cover is a collection $C$ of subsets of $V$ such that each element $c$ of $C$ is a clique ($c \times c \subseteq E$) and $G$ is the union of these cliques ($E = \...
- 683
3
votes
1
answer
565
views
Comparison between the maximum clique and maximum biclique problem
It seems to be commonly believed that the maximum biclique problem (on a bipartite graph) is more difficult than the original maximum clique problem. Is there a formal proof for this claim? (For ...
- 792
3
votes
0
answers
138
views
Fastest known algorithm to enumerate k-cliques in a graph for fixed k
Is the best known algorithm for finding all $k$-cliques in a graph with $n$ nodes, for a fixed $k$, given by https://theory.stanford.edu/~virgi/combclique-ipl-g.pdf ?
The time-complexity of the ...
- 189
3
votes
0
answers
183
views
$CIS_G$ problem deterministic lower bound
In notes, http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf, it is mentioned towards end of section $4$ that http://dl.acm.org/citation.cfm?id=237817 shows that ...
- 12.5k
2
votes
2
answers
184
views
Separating 2-SAT from Clique
Since the P vs. NP problem is still an open problem, 2-SAT and Clique might both be in P if P = NP. Is there any known complexity measure whatsoever that is already mathematically proven to ...
- 414
2
votes
2
answers
1k
views
$k$-clique in $k$-partite graph
Is the decision whether a $k$-clique exists in a $k$-partite graph NP-hard?
I have found only a very limited number of references on this problem, and they seem to be concerned with heuristics to ...
- 139
2
votes
1
answer
181
views
Decomposing complete graphs into clique-free graphs of certain size
Modified in accordance with Tsuyoshi's comment which seems to generalize.
Let $K_{m}$ be a complete graph on $m$ vertices. Is there a way to partition the graphs in to sets of graphs that have no ...
- 2,198
2
votes
1
answer
2k
views
Maximum clique algorithm on undirected graph
Recently I learned about maximum cliques. For fun I came up with an algorithm (described below) to find the maximum cliques in an undirected graph. I'd just like some help constructing a graph s.t. ...
- 131
2
votes
1
answer
773
views
Heuristics for the minimum-weight $k$-clique problem
Hello
Does someone have an idea for heuristics for the problem:
Given undirected weighted(weights on edges) complete
graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number of ...
- 189
2
votes
1
answer
227
views
Will core decomposition get a maximal clique?
I have read David Eppstein's paper about maximal clique enumeration by using degeneracy order. It has mentioned the core decomposition, which is removing the vertex with the smallest degree ...
- 23
2
votes
1
answer
604
views
Max weight k-clique
Given an edge-weighted directed complete graph $G = (V,A)$, the maximum weight clique of fixed size $k$ ($k$ is a constant) can be identified in polynomial time with a brute-force algorithm, however ...
- 21
2
votes
1
answer
742
views
Fast approximation of (vertex) clique cover
I'm looking for a fast algorithm to find a clique cover on an undirected unweighted graph.
I'm not looking for an optimal solution (ie minimal number of cliques). Obviously I'm also not looking for a ...
- 131
2
votes
1
answer
940
views
How to approximate minimum clique edge cover
I'd like to take an undirected graph and express it (meaning all of its edges) using only cliques (ideally minimizing their sum cardinality).
It's clear that actually finding the minimum solution is ...
- 916
2
votes
1
answer
275
views
Algorithms for finding all cliques of a given degree in a graph
Consider a graph with $n$ vertices and maximum degree $Δ$. I would like to obtain all $s$ cliques, where $s≤Δ$ and both of them are small compared to $n$.
Bron-Kerbosch algorithm gives all maximal ...
- 121