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
- References:
- Finding k-clique
- From: "Paulu" <ute.paul@gmail.com>
- Finding k-clique