The clique tag has no wiki summary.
7
votes
4answers
451 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? ...
1
vote
0answers
43 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 ...
2
votes
1answer
125 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 ...
18
votes
5answers
565 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
137 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 ...
10
votes
1answer
213 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 ...
2
votes
1answer
494 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. ...
8
votes
2answers
339 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. ...
3
votes
3answers
354 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: ...
7
votes
3answers
586 views
The number of cliques in a graph: the Moon and Moser 1965 result
I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't ...
11
votes
1answer
254 views
Is counting maximal cliques in an incomparability graph #P-complete?
This question is motivated by a MathOverflow question by Peng Zhang. Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs ...
1
vote
1answer
144 views
Decomposing complete graphs into clique-free graphs of certain size
Modified in accordance with Tsuyoshi's comment which seems to generalize.
Let $K_{m}$ be a complete graph on $m$ vertices. Is there a way to partition the graphs in to sets of graphs that have no ...
2
votes
4answers
708 views
Finding cliques in a big graph
I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques ...
7
votes
3answers
334 views
Graph classes in which CLIQUE is known to be NP-hard?
Given a graph $G$ and a positive integer $k$, the CLIQUE problem asks if $G$ contains a clique (complete subgraph) on at least $k$ vertices. This problem is long known to be NP-complete --- in fact, ...
2
votes
1answer
316 views
Heuristics for the minimum-weight $k$-clique problem
Hello
Does someone have an idea for heuristics for the problem:
Given undirected weighted(weights on edges) complete
graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number ...
7
votes
1answer
365 views
Max-clique in line graph of hypergraph
Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph ...
14
votes
2answers
438 views
Hardness of parameterized CLIQUE?
Let $0\le p\le 1$ and consider the decision problem
CLIQUE$_p$
Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges
Question: does $G$ contain a clique on at ...
7
votes
1answer
376 views
Algorithms and computational complexity of clique and biclique covers
I've been reading a paper by a mathematical chemist. He proposes some indices to measure the complexity of molecules. From here on in, instead of molecules, think undirected connected graphs: a ...
