[Rule] HighlyConnectedDeletion to ILP

[zhangjieqingithub]

Source

HighlyConnectedDeletion

Target

ILP

Motivation

This is the natural first companion rule for HighlyConnectedDeletion: it gives the model an immediate solver path and avoids leaving it orphaned in the reduction graph.

The source paper uses integer linear programming with column generation. The formulation below is an inference from that approach: a set-partitioning ILP over feasible clusters.

Reference

• Falk H�cffner, Christian Komusiewicz, Adrian Liebtrau, Rolf Niedermeier, "Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage," IEEE/ACM Transactions on Computational Biology and Bioinformatics 11(3):455-467, 2014. https://doi.org/10.1109/TCBB.2013.177

Reduction Algorithm

Let the source instance be a simple undirected graph G = (V, E).

Define a subset S subseteq V to be a feasible cluster if either:

• |S| = 1, or
• |S| >= 3 and the induced graph G[S] is highly connected.

Let C(G) be the family of all feasible clusters.

Construct a binary ILP with one variable x_S for each S in C(G), where:

• x_S = 1 iff S is chosen as one block of the final partition.

Add partition constraints:

• for every vertex v in V,
  sum_{S in C(G), v in S} x_S = 1

These force the selected feasible clusters to form a partition of V.

Set the objective to maximize the number of kept edges:

• max sum_{S in C(G)} |E(G[S])| * x_S

Correctness intuition:

• every chosen block is either a singleton or a highly connected cluster
• the partition constraints ensure every vertex belongs to exactly one chosen block
• all edges with both endpoints inside the same chosen block are kept
• all edges crossing two different chosen blocks are deleted
• therefore maximizing kept internal edges is equivalent to minimizing deleted edges, since |E| is constant:
  deleted_edges = |E| - kept_edges

Size Overhead

Let n = |V|, and let c(G) = |C(G)| be the number of feasible clusters.

Exact target size:

• num_vars = c(G)
• num_constraints = n

Worst-case bound suitable for registry overhead discussion:

• num_vars <= 2^num_vertices
• num_constraints = num_vertices

Validation Method

• Compare the ILP optimum against brute-force edge-deletion search on small graphs.
• Verify that each selected ILP block is either a singleton or induces a highly connected graph.
• Verify that the selected blocks form a partition of V.
• Check that the source objective equals |E| - the ILP objective value.

Example

Take the source graph

• V = {0,1,2,3}
• E = {{0,1}, {0,2}, {1,2}, {2,3}}

The feasible clusters are:

• singletons {0}, {1}, {2}, {3}
• the triangle {0,1,2}

There are no other feasible clusters:

• {2,3} is not allowed because a 2-vertex component is not a valid cluster
• any larger set containing 3 is not highly connected

Introduce ILP variables:

• x_{0}, x_{1}, x_{2}, x_{3}, x_{012}

Partition constraints:

• x_{0} + x_{012} = 1
• x_{1} + x_{012} = 1
• x_{2} + x_{012} = 1
• x_{3} = 1

Objective:

• max 0*x_0 + 0*x_1 + 0*x_2 + 0*x_3 + 3*x_{012}

The optimal ILP solution is:

• x_{012} = 1
• x_{3} = 1
• all other variables 0

This keeps 3 internal edges, so the source deletion value is
|E| - 3 = 4 - 3 = 1,
corresponding exactly to deleting the edge {2,3}.

BibTeX

@article{HueffnerKomusiewiczLiebtrauNiedermeier2014,
  author  = {Falk H{"u}ffner and Christian Komusiewicz and Adrian Liebtrau and Rolf Niedermeier},
  title   = {Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage},
  journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
  volume  = {11},
  number  = {3},
  pages   = {455--467},
  year    = {2014},
  doi     = {10.1109/TCBB.2013.177},
  url     = {https://doi.org/10.1109/TCBB.2013.177}
}