# Questions tagged [clique]

The tag has no usage guidance.

71 questions
Filter by
Sorted by
Tagged with
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)?
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 ...
1 vote
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 ...
1 vote
118 views

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 ...
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 ...
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 ...
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 ...
226 views

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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
166 views

1 vote
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$ ...
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 ...
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 ...
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 ... 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 ...
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 ...
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 ...
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, ...
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? ...
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 : www.nada.kth.se/~johanh/cliqueinap.ps In fact, I only want to understand the proof of ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1k views

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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...