Ask Your Question

Way to solve max_split enumeration

asked 2017-07-16 05:32:13 -0500

AlexJ gravatar image

Hello everyone, I try to solve a problem on graphs. The graphs contain two types of nodes, a first type linked together containing max_cliques that I seek to determine. A second one connected only to the first.

For the moment I enumerate the biggest cliques of the first type, then determines for each the number of nodes of the second type related to this one. Finally I list the one with the largest number of nodes of the second type.   So I'm looking to find the biggest split graph.

Do you have an idea to improve my current way?

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted

answered 2017-07-21 10:25:22 -0500

tmonteil gravatar image

updated 2017-07-21 10:29:36 -0500

You can use integer linear programming as follows:

For each vertex v of your graph, assign two binary variables c[v] and i[v], telling whether the vertex belongs to the clique or the independent set you are looking for.

You want the largest induced split graph, so the objective function you want to maximize is the sum of c[v]+i[v] over all vertices.

The two sets are disjoints, so you should add the constraint that, for each vertex v, c[v]+i[v] <= 1.

The vertices with c[v] == 1 is a clique, so you have to add the following constraint: for each non-edge (v,w), the c[v]+c[w] <= 1 (i.e. between two elements of the clique, there must be an edge).

The vertices with i[v] == 1 is an independent set, so you have to add the following constraint: for each edge (v,w), the i[v]+i[w] <= 1 (i.e. between two elements of the independent set, there must be a non-edge).

Note that for the last two types of constraints (which are dual), you can make a single loop over pairs of vertices, and add the constraint depending on whether they are connected by an edge or not.

Then, just let Sage (or some ILP package it contains) solve the problem for you !

Do not hesitate to ask for more details if you do not succeed to implement it.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2017-07-16 05:32:13 -0500

Seen: 255 times

Last updated: Jul 21