Questions tagged [clique]
The clique tag has no usage guidance.
71
questions
2
votes
1
answer
93
views
clique problem in graphs with bounded degree
Is the problem of finding a clique of size $d$ in a graph of maximum degree $d$ NP-complete ($d$ part of the input)?
- 23
2
votes
0
answers
57
views
Is Finding an *Unbalanced* Biclique in Bipartite Graphs Hard?
In the balanced biclique in bipartite graphs (MBB) problem we are given a bipartite graph $G = (L,R,E), |L| = |R| = n$ and the goal is to find an induced subgraph of $G$, $G' = (L',R',E')$, with as ...
- 113
1
vote
1
answer
122
views
Approximation algorithm for balanced bipartite independent set?
The Problem: Given a bipartite graph $G = (L,R,E)$ with $|L|=|R|=n$, the balanced bipartite independent set problem asks us to output the largest vertex subsets $A\subseteq L, B\subseteq R$ of equal ...
- 53
1
vote
0
answers
118
views
Is finding a very large clique NP-hard?
We know that, unless P=NP, for any $\epsilon$ we can't distinguish in polynomial time between the two cases:
There exists a clique of size at least $n^{1-\epsilon}$
All cliques have size at most $n^\...
- 201
2
votes
2
answers
226
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
0
votes
0
answers
87
views
Large CLIQUE approximation
I am interested in algorithms to identify large cliques in graphs where the largest clique is a large fraction (definitely greater than half, perhaps as great as 4/5) of the total number of vertices.
...
- 121
1
vote
2
answers
187
views
Maximum cliques of the transitive closure of a chordal DAG
Let $G=(V,A)$ be a directed acyclic graph, for which the underlying
undirected graph is chordal (so that every induced cycle in the
underlying undirected graph is a triangle).
It is known that in a ...
- 11
3
votes
1
answer
136
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 = \...
- 693
17
votes
0
answers
597
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,166
3
votes
1
answer
138
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
-1
votes
1
answer
141
views
approximate maximum clique given vertex cover
I have a non optimal vertex cover of size k of a graph G, and I want to get a (1+epsilon)-approximation kernel of size linear in k for maximum clique of G. One thing I got is that every clique in G ...
- 1
3
votes
0
answers
295
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 ...
- 209
0
votes
1
answer
226
views
Dividing a complete graph into two cliques with maximal sum of edge weights
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\...
- 11
2
votes
0
answers
183
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_{...
- 251
2
votes
1
answer
253
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
7
votes
2
answers
372
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
2
votes
1
answer
289
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
7
votes
0
answers
99
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,227
3
votes
1
answer
682
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 ...
- 31
1
vote
1
answer
166
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 $...
- 12.7k
5
votes
2
answers
346
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
-2
votes
1
answer
673
views
Finding All Cliques of an Undirected Graph
How can I list all cliques of an Undirected Graph ? (Not all maximal cliques, like the Bron-Kerbosch algorithm)
- 1
0
votes
1
answer
448
views
Paritioning a graph into clique and independent set
I am interested in the complexity of the following problems:
Input: an undirected graph $G = \langle V, E \rangle$
Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $...
- 121
1
vote
1
answer
273
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$ ...
- 21
7
votes
1
answer
1k
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 ...
- 5,065
7
votes
1
answer
264
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,227
5
votes
1
answer
433
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
13
votes
1
answer
3k
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.9k
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.9k
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 ...
- 5,065
14
votes
0
answers
679
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, ...
- 5,065
10
votes
1
answer
921
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?
...
- 5,065
2
votes
0
answers
180
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 ...
- 137
6
votes
0
answers
182
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
1
answer
486
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
0
votes
1
answer
202
views
Clique-Percolation Algorithm's "corner cases"
I'm programming an implementation of the Clique-Percolation algorithm, but I have many doubts about some corner cases.
Imagine we want to find the communities of a graph using $k=4$. We are lucky and ...
- 143
3
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 ...
- 149
3
votes
0
answers
188
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.7k
3
votes
1
answer
593
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 ...
- 822
7
votes
1
answer
713
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
-2
votes
1
answer
1k
views
Finding cliques in weighted graph
We have given a weighted graph $G=\{V,E\}$, where $V=\{v_1, v_2,...,v_n\}$, and for all $i,j$, the weight of edges $w(v_i, v_j)\in (0,W)$. And we have also given a weight threshold s $w$ (where $0<...
- 639
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
1
vote
0
answers
178
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 ?
- 1,006
4
votes
1
answer
210
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(...
- 575
2
votes
1
answer
799
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
0
votes
3
answers
281
views
Terminology for complete k-partite graph where k is not fixed
Is there a better term for "complete k-partite graph" in the case where k is not fixed? If I say "complete k-partite graph", people tend to assume "for some particular k".
In other words, what's a ...
- 916
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
5
votes
1
answer
505
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
4
votes
3
answers
759
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
9
votes
0
answers
260
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