Revision history [back]

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 clique, there must be a non-edge).

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.

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 clique, independent set, there must be a non-edge).

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.

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, 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.

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, 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.