[Rule] MaximalIS to ILP

[GiggleLiu]

Source

MaximalIS (Maximum Weight Maximal Independent Set)

Target

ILP (Integer Linear Programming)

Motivation

• MaximalIS is completely isolated in the reduction graph — zero incoming and zero outgoing reductions
• Connects MaximalIS to the ILP hub (12+ incoming reductions), enabling ILP-based solving
• Classic formulation: a maximal independent set is exactly an independent dominating set

Reference

Pinacho Davidson, P., Blum, C., & Lozano, J. A. (2018). The weighted independent domination problem: Integer linear programming models and metaheuristic approaches. European Journal of Operational Research, 265(3), 860–871. DOI: 10.1016/j.ejor.2017.08.044

Reduction Algorithm

Given a MaximalIS instance with graph G = (V, E) and vertex weights w₁, ..., wₙ:

1. Create n = |V| binary variables x₁, ..., xₙ, where xᵢ = 1 means vertex i is in the independent set.
2. Set the objective to maximize Σᵢ wᵢ · xᵢ.
3. Independence constraints: For each edge (i, j) ∈ E, add xᵢ + xⱼ ≤ 1.
4. Maximality constraints: For each vertex i ∈ V, add xᵢ + Σ_{j ∈ N(i)} xⱼ ≥ 1.

Solution extraction: The binary vector (x₁, ..., xₙ) maps directly back — vertex i is selected if xᵢ = 1.

Correctness: The independence constraints ensure no two adjacent vertices are selected (independent set). The maximality constraints ensure every unselected vertex has at least one selected neighbor — so no vertex can be added, making the set maximal. The feasible region is exactly the set of maximal independent sets, and the objective selects the maximum-weight one.

Size Overhead

Target metric	Formula
num_vars	num_vertices
num_constraints	num_edges + num_vertices

Validation Method

Closed-loop test: construct a MaximalIS instance, reduce to ILP, solve ILP with brute force, extract solution back to MaximalIS, and verify optimality matches brute-force search over all maximal independent sets.

Example

Source (MaximalIS): 6 vertices, edges {(0,1), (0,2), (1,2), (2,3), (3,4), (4,5)}, weights = [1, 4, 1, 3, 1, 2].

Graph structure: triangle on {0,1,2} with path 3–4–5 attached at vertex 2.

All maximal independent sets: {0,3,5} (weight 6), {0,4} (weight 2), {1,3,5} (weight 9), {1,4} (weight 5), {2,4} (weight 2), {2,5} (weight 3).

Target (ILP):

• Variables: x₀, x₁, x₂, x₃, x₄, x₅ ∈ {0, 1}
• Maximize: x₀ + 4x₁ + x₂ + 3x₃ + x₄ + 2x₅
• Independence (6 constraints): x₀+x₁ ≤ 1, x₀+x₂ ≤ 1, x₁+x₂ ≤ 1, x₂+x₃ ≤ 1, x₃+x₄ ≤ 1, x₄+x₅ ≤ 1
• Maximality (6 constraints): x₀+x₁+x₂ ≥ 1, x₁+x₀+x₂ ≥ 1, x₂+x₀+x₁+x₃ ≥ 1, x₃+x₂+x₄ ≥ 1, x₄+x₃+x₅ ≥ 1, x₅+x₄ ≥ 1

Optimal ILP solution: (0, 1, 0, 1, 0, 1) with objective value 9.
Extracted MaximalIS solution: Select vertices {1, 3, 5}, total weight = 4 + 3 + 2 = 9.

This example is non-trivial because the triangle on {0,1,2} creates dense constraint interactions (at most one vertex selectable from the triangle), six distinct maximal independent sets exist with weights ranging from 2 to 9, and a suboptimal maximal IS like {0,3,5} (weight 6) would be returned by an incorrect reduction that doesn't properly encode the objective.

BibTeX

@article{PinachoDavidson2018,
  author    = {Pinacho Davidson, Pedro and Blum, Christian and Lozano, Jos{\'e} A.},
  title     = {The weighted independent domination problem: {I}nteger linear programming models and metaheuristic approaches},
  journal   = {European Journal of Operational Research},
  volume    = {265},
  number    = {3},
  pages     = {860--871},
  year      = {2018},
  doi       = {10.1016/j.ejor.2017.08.044},
}