4
$\begingroup$

This question is quite specific and practical. I hope it is still relevant for MO and will not be removed.

I have a collection $\mathcal{C}$ of graphs having from 5000-6000 vertices and edge density about $0.5,$ the average degree being quite close to half the number of vertices.

I need to determine whether a graph $G \in \mathcal{C}$ has a clique greater than some given constant $k$, for my purpose I can assume $k = 50.$

Using cliquer on these graphs does not produce any result in a reasonable amount of time and since it is not required that I compute the clique number exactly I improvised the following way to test whether a graph has a clique of size $> k$ or not.

A vertex $v$ of $G$ is uninvolved if $v$ is not contained in a clique of size $> k.$

Observe that if $v$ is uninvolved then $G$ has a large clique if and only if $G-v$ has.

Note also that $v$ is uninvovled if and only if the clique number of the graph induced by $N(v)$ is not greater than $k-2.$ This gives us a recursive way of determing whether our graph has a large clique or not.

Now, I've noticed that the graphs in $\mathcal{C}$ have quite some amount of symmetry. They are far from being vertex transitive, but their automorphism group partitions the vertex set into orbits of nice size and hence one can use the following idea.

  1. Pick a vertex $v$ such that $N(v)$ is small.

    2.1 If the graph induced by $N(v)$ has a large clique report it.

    2.2 Let $\mathcal{O}$ be the orbit of $v$ in $G.$ Test if $G-\mathcal{O}$ has a large clique.

The above is implemented as a Sage program here.

The described method works fine but is still too slow given that I need to test this on a large collection of graphs. I've read some literature about cliques and the respective upper bounds but I was not able to find a good bound or practical method for the graphs in $\mathcal{C}.$ The only property that I am thus able to exploit is their symmetry.

My question therefore is

  1. Are there any other invariants I could check to speed up the above computation?
  2. Is there any other that works well when one only needs to verify whether a certain graph has a large clique or not?
  3. Are there any other approaches you for solving this efficiently?

Edit. Here is one example of a graph given as a list of edges.

$\endgroup$
14
  • $\begingroup$ It's worth noting that detecting whether a general graph has a k-clique is NP-complete. $\endgroup$
    – Ben Barber
    Mar 17, 2014 at 11:00
  • 1
    $\begingroup$ The little known program MaxCliqueDyn to be found at sicmm.org/~konc/maxclique often supersedes cliquer. Maybe it helps in your situation. $\endgroup$ Mar 17, 2014 at 11:12
  • $\begingroup$ Hey, perhaps we should add it to Sage if it is better than Cliquer O_o $\endgroup$ Mar 17, 2014 at 12:22
  • $\begingroup$ Have you tried independent set on the complement using MILP? $\endgroup$
    – joro
    Mar 17, 2014 at 13:09
  • 1
    $\begingroup$ I wonder if you can use spectral properties? For example: Alon, Noga, Michael Krivelevich, and Benny Sudakov. "Finding a large hidden clique in a random graph." SODA. 1998. $\endgroup$ Mar 17, 2014 at 18:25

4 Answers 4

1
$\begingroup$

One can compute upper bounds (which are sometimes tight) on the size of cliques in $G$.

A standard trick would be to compute Lovasz $\theta$-function $\theta(G)$ of $G$ (or a slightly better, Schrijver's variant of $\theta$, usually called $\theta'$), or some (weaker in general) upper bound on the clique number. This is a particular kind of a semidefinite programming problem. I have Sage code that can in principle be used for this – I have not found time (or a student to work on this) to properly include it into Sage. For graphs of this size it is however a challenge to make it run fast enough. (There are a number of stand-alone implementations of this computation available, too).

Using symmetries might reduce the size of the problem quite considerably - you would basically need one variable per edge/non-edge orbit of your automorphism group.

Of course there is no guarantee that it will be useful, as it could only (potentially) rule out existence of $k$-clique in $G$, by establishing that $\theta'(G)$ < $k$.

$\endgroup$
1
$\begingroup$

Determining, even approximately, the largest clique in a graph is known to be NP-hard. You cannot determine with any degree of accuracy the largest clique for a given graph in polynomial time.

From this:

Definition 2.2. GapCLIQUE ρ :Given ρ ≤ 1, a graph G and an integer k, we wish to distinguish between the following two cases:

YES: ω(G) ≥ k, G has a clique of size k

NO: ω(G) < ρk, G has no clique of size ≥ ρk.

Theorem 2.7. ∀ ρ > 0, GapCLIQUE is NP -hard.

$\endgroup$
1
$\begingroup$

May be more relevant than hardness of approximation results is the fact that finding a clique of size $k$ is complete for the class W[1]. This means that an algorithm with running time $f(k)\cdot n^c$ is unlikely to exist, where $f$ is a function independent of $n$ and $c$ is a constant independent of $k$. Particularly, if such an algorithm existed, then 3SAT would be solvable in time $2^{o(n)}$, which contradicts the Exponential Time Hypothesis (ETH), and would be a fairly big surprise. In fact we even know that an algorithm with running time $f(k)\cdot n^{o(k)}$ already contradicts ETH. For background on ETH and this type of negative results you can also check this nice survey by Lokshtanov, Marx, and Saurabh.

$\endgroup$
0
$\begingroup$

This is a simple idea and I'm not sure how useful it will be, but I'll throw it in anyway. Call your current graph $G$. If $G$ has a vertex $v$ of low degree, you can eliminate it and its orbit quickly, and if not then the algorithm gets bogged down. So when there are no vertices of low degree left, it might be worth instead looking for vertices $v$ such that $G[N(v)]$ has many vertices of low degree. Thus the algorithm will be able to eliminate a lot of vertices from $G[N(v)]$ quite quickly in the recursive step, and hopefully $v$ itself will be eliminated quite quickly. Of course this will add a lot of overhead, so it might not be worth the trade-off.

$\endgroup$
6
  • $\begingroup$ Dear John, the graph in question has no vertices of small degree (the minimum degree is about at least 1800 in all graphs in $\mathcal{C}$) $\endgroup$
    – Jernej
    Mar 17, 2014 at 16:19
  • $\begingroup$ I don't think that's a big problem, though? When I say that $G[N(v)]$ should have many vertices of low degree, I mean low degree in $N(v)$ rather than in $G$ itself. So the approach should only fail completely if every pair of vertices has a large common neighbourhood. $\endgroup$
    – John
    Mar 17, 2014 at 17:20
  • $\begingroup$ Yes. The common neighbourhood of any pair of vertices is still too large though. $\endgroup$
    – Jernej
    Mar 17, 2014 at 17:46
  • $\begingroup$ Silly question: is it true that if you have a set of $t$ vertices, their common neighbourhood has size roughly $2^{-t}\cdot 5000$? (For values of $t$ which are small enough that you can test this easily.) $\endgroup$
    – John
    Mar 17, 2014 at 17:57
  • $\begingroup$ I haven't tested this formally but given what I know about the graphs I am not sure this holds - do you have any kind of motivation for this? $\endgroup$
    – Jernej
    Mar 17, 2014 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.