Questions tagged [clique]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
107 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^\...
user avatar
  • 191
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 ...
user avatar
  • 414
0 votes
0 answers
80 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. ...
user avatar
1 vote
2 answers
152 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 ...
user avatar
3 votes
1 answer
123 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 = \...
user avatar
17 votes
0 answers
565 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 ...
user avatar
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 ...
user avatar
  • 93
-1 votes
1 answer
109 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 ...
user avatar
3 votes
0 answers
133 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 ...
user avatar
  • 189
0 votes
1 answer
166 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 $\...
user avatar
  • 11
2 votes
0 answers
175 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_{...
user avatar
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 ...
user avatar
  • 23
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 ...
user avatar
  • 203
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 ...
user avatar
  • 121
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 ...
user avatar
  • 1,095
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 ...
user avatar
  • 21
1 vote
1 answer
163 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 $...
user avatar
  • 12.5k
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 ...
user avatar
-2 votes
1 answer
651 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)
user avatar
  • 1
0 votes
1 answer
349 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 $...
user avatar
1 vote
1 answer
240 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$ ...
user avatar
  • 21
7 votes
1 answer
958 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 ...
user avatar
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 ...
user avatar
  • 1,095
5 votes
1 answer
421 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
14 votes
0 answers
648 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, ...
user avatar
10 votes
1 answer
845 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? ...
user avatar
2 votes
0 answers
170 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 ...
user avatar
  • 137
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, ...
user avatar
  • 656
5 votes
1 answer
393 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 ...
user avatar
  • 53
0 votes
1 answer
195 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 ...
user avatar
  • 143
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 ...
user avatar
  • 139
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 ...
user avatar
  • 12.5k
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 ...
user avatar
  • 792
7 votes
1 answer
641 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 ...
user avatar
  • 641
-2 votes
1 answer
967 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<...
user avatar
  • 629
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?
user avatar
  • 53
1 vote
0 answers
177 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 ?
user avatar
  • 1,006
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(...
user avatar
  • 551
2 votes
1 answer
740 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 ...
user avatar
  • 131
0 votes
3 answers
276 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 ...
user avatar
  • 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 ...
user avatar
  • 1,006
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 ...
user avatar
  • 916
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 ...
user avatar
  • 43
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$ ...
user avatar
  • 1,897
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)|...
user avatar
  • 171
0 votes
0 answers
197 views

Finding assignment-minimum complete k-partite graph cover

Is there any work on approximation algorithms (or exact algorithms) for finding an assignment-minimum cover of an arbitrary graph using complete k-partite subgraphs? I'm assuming this problem is NP-...
user avatar
  • 916
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'...
user avatar