[Rule] MaximumDomaticNumber to ILP #963
Description
Motivation
Direct ILP formulation for MaximumDomaticNumber. Companion issue for #878 (MaximumDomaticNumber model). Enables ILP-based solving.
Source
MaximumDomaticNumber
Target
ILP (Integer Linear Programming)
Reference
Standard ILP formulation for domatic partition; see Kaplan and Shamir (1994).
Reduction Algorithm
Input: A graph G = (V, E) with n = |V| vertices.
- Create binary variables x_{v,i} ∈ {0, 1} for each vertex v ∈ V and each potential partition index i ∈ {1, ..., n}, where x_{v,i} = 1 means vertex v is assigned to set V_i.
- Create binary variables y_i ∈ {0, 1} for each i ∈ {1, ..., n}, where y_i = 1 means set V_i is non-empty.
- Partition constraint: for each vertex v, Σ_i x_{v,i} = 1 (each vertex in exactly one set).
- Domination constraint: for each vertex v and each set i, x_{v,i} + Σ_{u ∈ N(v)} x_{u,i} ≥ y_i (if set V_i is used, v must be in V_i or adjacent to some member of V_i).
- Linking: y_i ≤ Σ_v x_{v,i} for each i (y_i = 1 only if V_i is non-empty).
- Objective: maximize Σ_i y_i.
Solution extraction: Read x_{v,i} = 1 to determine vertex-to-set assignment.
Size Overhead
| Code metric | Formula |
|---|---|
num_variables |
n^2 + n |
num_constraints |
n + n^2 + n |
Where n = number of vertices.
Validation Method
Closed-loop test: construct a graph, reduce to ILP, solve, extract partition, verify all parts are dominating sets.
Example
Source: Path P3: v0—v1—v2, edges {(0,1),(1,2)}.
ILP: x_{v,i} for v ∈ {0,1,2}, i ∈ {1,2,3}; y_1, y_2, y_3.
- Partition: x_{0,1}+x_{0,2}+x_{0,3}=1, etc.
- Domination at v0 for set i: x_{0,i}+x_{1,i} ≥ y_i
- Domination at v2 for set i: x_{2,i}+x_{1,i} ≥ y_i
- Domination at v1 for set i: x_{1,i}+x_{0,i}+x_{2,i} ≥ y_i
Optimal: y_1=1, y_2=1, y_3=0 → Max(2). Partition: V_1={v0,v2}, V_2={v1}.