Questions tagged [clique]
The clique tag has no usage guidance.
59
questions
21
votes
5answers
2k 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 ...
17
votes
2answers
676 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 ...
15
votes
2answers
832 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 ...
15
votes
1answer
219 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 ...
14
votes
0answers
582 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, ...
13
votes
1answer
541 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 (...
11
votes
1answer
553 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-...
10
votes
4answers
3k 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 ...
10
votes
1answer
830 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 ...
10
votes
1answer
199 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 ...
9
votes
2answers
711 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. ...
9
votes
1answer
436 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?
...
9
votes
0answers
232 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$ ...
8
votes
1answer
625 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 ...
8
votes
1answer
490 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 ...
7
votes
4answers
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'...
7
votes
3answers
474 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, ...
7
votes
1answer
194 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 ...
7
votes
2answers
245 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 ...
7
votes
1answer
452 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 ...
7
votes
1answer
282 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)|...
7
votes
0answers
87 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 ...
6
votes
1answer
644 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 ...
6
votes
0answers
170 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, ...
5
votes
1answer
325 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 ...
5
votes
2answers
219 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 ...
5
votes
2answers
986 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?
5
votes
1answer
349 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 ...
5
votes
1answer
303 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 ...
4
votes
3answers
2k 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: ...
4
votes
3answers
610 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 ...
4
votes
1answer
190 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(...
3
votes
4answers
2k 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 ...
3
votes
2answers
2k 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 ...
3
votes
1answer
513 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 ...
3
votes
0answers
179 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 ...
2
votes
2answers
879 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 ...
2
votes
1answer
179 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
votes
1answer
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. ...
2
votes
1answer
680 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 ...
2
votes
1answer
170 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 ...
2
votes
1answer
408 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 ...
2
votes
1answer
618 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 ...
2
votes
1answer
871 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 ...
2
votes
0answers
149 views
A variant of the Maximum Weight Clique problem
I am trying to solve a problem that I could reduce to the following:
Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum_{...
1
vote
1answer
147 views
Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known
Given a $k>0$ and a graph $G(V,E)$ with known independence number $\sqrt{|V|}\leq\alpha(G)\leq\alpha\sqrt{|V|}$ and chromatic number $\frac1\beta\sqrt{|V|}\leq\chi(G)\leq\sqrt{|V|}$ for some fixed $...
1
vote
1answer
153 views
Maximal Clique partition of vertices with smallest number of cut edges
I am given a simple undirected graph $G(V, E)$. I want to partition $V$ into $b$ Maximal cliques: $\{C_1, C_2, ..., C_b\}$ such that the number of edges that cut across two cliques is the minimum. $b$ ...
1
vote
0answers
196 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 ...
1
vote
0answers
130 views
hardness of approximating clique: how using FGLSS reduction with PCP verifier of hastad
I try to understand the $n^{1-\epsilon}$ hardness of approximating clique for any $\epsilon$ provided in [1]: www.nada.kth.se/~johanh/cliqueinap.ps
In fact, I only want to understand the proof of ...
1
vote
0answers
173 views
Minimum Clique edge cover to cilque vertex cover
Suppose, there is an algorithm for enumerating minimum clique edge cover. Is it always possible to convert the algorithm to enumerate clique vertex cover ?
