MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Finding k-clique

  • To: mathgroup at smc.vnet.net
  • Subject: [mg65516] Re: [mg65498] Finding k-clique
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Thu, 6 Apr 2006 06:51:57 -0400 (EDT)
  • References: <200604051055.GAA21725@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Paulu wrote:
> I would like to get the number of k-cliques in a Graph and a Function
> that returns all k-Cliques.
> Combinatorica provides only MaximumClique[g], which returns only the
> largest Clique in a Graph.
> Does anybody have an idea how to solve this problem in mathematica?
> 
>  I found a method in Java: Finding k-cliques using Backtracking with
> cutoffs pruning.  Is ist possible to translate a Java Code to
> Mathematica?


 From the documentation:

MaximumClique::usage = "MaximumClique[g] finds a largest clique
in graph g. MaximumClique[g, k] returns a k-clique, if such a
thing exists in g; otherwise it returns {}."

So one approach would be as below.

Input: Graph G.

(1) Push {G,0} onto a stack.
(2) In a loop while the stack is nonempty:
   (3) Pop off the top subproblem {H,k} where
       H is a graph and k an integer.
   (4) Find one k-clique. Call the set of vertices {v[1],...,v[k]}.
       Store the k-clique found in the result R (use e.g. Sow,
       and Reap the result when finished).
   (5) Iteratively push onto the stack the following subproblems:
       Find all k-cliques for the {graph,index} pair {G[j],j},
       where j>k and G[j] is the subgraph G-v[j], (so you have to
       remove vertex v[j] and its edges). The inequality condition
       is to avoid repetition such as working with the subgraph
       (G-v[1])-v[2] and also with (G-v[2])-v[1].

I have not tried this but I think it can be made to work, with whatever 
tweaking is necessary to correct any parts that are, well, not correct.

To address your second question, yes. (Proof of concept: First translate 
the Java to a Turing machine, then go from that to Mathematica.) Really 
the details would depend on how well the person doing the translating 
knows the two languages and knows the problem area. Offhand I do not 
know of an automatic Java->Mathematica translation program but from time 
to time I am surprised to learn such things exist at least for language 
subsets.

Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: graphic inside a gridbox
  • Next by Date: Re: graphic inside a gridbox
  • Previous by thread: Finding k-clique
  • Next by thread: Return, behaviour of