Questions tagged [clique]

The tag has no usage guidance.

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
14
votes
0answers
594 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
0answers
234 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
0answers
92 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
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, ...
3
votes
0answers
63 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 ...
3
votes
0answers
180 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
0answers
152 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
0answers
205 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
144 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
174 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
vote
0answers
866 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 ...
0
votes
0answers
190 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-...