Questions tagged [clique]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
67 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 $\...
2
votes
0answers
148 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_{...
2
votes
1answer
159 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 ...
7
votes
2answers
242 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 ...
1
vote
0answers
193 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 ...
7
votes
0answers
86 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 ...
2
votes
1answer
398 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
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 $...
5
votes
2answers
211 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 ...
-2
votes
1answer
520 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)
0
votes
1answer
221 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 $...
1
vote
1answer
151 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$ ...
6
votes
1answer
633 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 ...
7
votes
1answer
189 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 ...
5
votes
1answer
348 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 ...
10
votes
1answer
791 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 ...
15
votes
1answer
214 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 ...
15
votes
2answers
819 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 ...
14
votes
0answers
578 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, ...
9
votes
1answer
413 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? ...
1
vote
0answers
127 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 ...
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
302 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 ...
0
votes
1answer
184 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 ...
2
votes
2answers
872 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 ...
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 ...
3
votes
1answer
511 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 ...
7
votes
1answer
446 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 ...
-2
votes
1answer
732 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<...
5
votes
2answers
975 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?
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 ?
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(...
2
votes
1answer
614 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 ...
0
votes
3answers
251 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 ...
3
votes
2answers
1k 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 ...
5
votes
1answer
323 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 ...
4
votes
3answers
603 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 ...
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$ ...
7
votes
1answer
281 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)|...
0
votes
0answers
182 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-...
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'...
0
votes
1answer
143 views

Help with the definition of clique percolation

So I can find the Wiki article okay, as I think I understand that this is a definition of a special community in a graph. However their image in Fig. 1 confuses me from the description. As I ...
1
vote
0answers
851 views

Finding minimum weight $k$ cliques in a complete graph

For an undirected weighted complete graph $G = (V, E)$. Assuming the edge weight indicates the similarity between different nodes, the smaller $w_{ij}$ is, it means $i$ and $j$ are more similar ...
2
votes
1answer
869 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 ...
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 ...
10
votes
1answer
198 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 ...
11
votes
1answer
538 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-...
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. ...
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. ...
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: ...