Update Graph.clique_maximum to use MILP

[nathanncohen]

This begins to be a joke, but there is a third method I had forgotten in #11846 and #11928 as noticed by Peter Mueller :-p

This patch updated clique_maximum to use the new MILP formulation of independent set !

Requires :

• Independent set through Linear Programming (sometimes, it is faster !) #11846
• Update Graph.clique_number to use MILP #11928

Apply:

• attachment: trac_11944.patch

Nathann

Depends on #11846
Depends on #11928

CC: @dcoudert

Component: graph theory

Author: Nathann Cohen

Reviewer: David Coudert

Merged: sage-4.8.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/11944

[dcoudert]

comment:2

Attachment: trac_11944.patch.gz

The patch is working correctly, and the documentation is displayed properly.

I have a question concerning the algorithms: wouldn't it be faster to first decompose the graph into 2-connected components, and then try the algorithm on each of them ? This could be interesting for sparse graphs.

[dcoudert]

Reviewer: David Coudert

[nathanncohen]

comment:3

Hello !!!

It would be, but not in this patch, as it does not do anything but asks for the "independent set algorithm" to do it.

The answer, however is "YES", and much more :

I interfaced some time ago an external C code for modular decomposition. With this decomposition, you obtain (given a graph) a recursive decomposition into connected components and anticonnected components (the complement of connectedcomponents). This is what we should use to first educe the graph, as this algorithm is very fast (though it will have no effect for random-looking graphs).

I have had it on my todo list for a while, and right now I am actually writing the ong-awaited Gurobi interface for Sage :-)

Nathann

[dcoudert]

comment:4

Thank you Nathann for the prompt answer.

So my review for this patch is positive.

[nathanncohen]

comment:5

Thaaaaaaaaaaaanks !! :-)

Nathann

[jdemeyer]

Changed dependencies from 11846, 11928 to #11846, #11928

[jdemeyer]

Merged: sage-4.7.3.alpha0

[jdemeyer]

Milestone sage-4.7.3 deleted

[jdemeyer]

Changed merged from sage-4.7.3.alpha0 to sage-4.8.alpha0