problemreductions/rules/
kclique_ilp.rs

1//! Reduction from KClique to ILP (Integer Linear Programming).
2//!
3//! The KClique decision problem can be formulated as a binary ILP:
4//! - Variables: One binary variable per vertex (0 = not in clique, 1 = in clique)
5//! - Constraints:
6//!   - Sum of x_v >= k (at least k vertices selected)
7//!   - x_u + x_v <= 1 for each non-edge (u, v) — at most one non-adjacent vertex pair selected
8//! - Objective: Minimize 0 (feasibility check only)
9//!
10//! The ILP is feasible if and only if the graph contains a clique of size at least k.
11
12use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
13use crate::models::graph::KClique;
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16use crate::topology::{Graph, SimpleGraph};
17
18/// Result of reducing KClique to ILP.
19///
20/// This reduction creates a binary ILP where:
21/// - Each vertex corresponds to a binary variable x_v
22/// - A cardinality constraint ensures at least k vertices are selected
23/// - Non-edge constraints ensure any two selected vertices are adjacent (forming a clique)
24/// - The empty objective makes this a feasibility problem
25#[derive(Debug, Clone)]
26pub struct ReductionKCliqueToILP {
27    target: ILP<bool>,
28}
29
30impl ReductionResult for ReductionKCliqueToILP {
31    type Source = KClique<SimpleGraph>;
32    type Target = ILP<bool>;
33
34    fn target_problem(&self) -> &ILP<bool> {
35        &self.target
36    }
37
38    /// Extract solution from ILP back to KClique.
39    ///
40    /// Since the mapping is 1:1 (each vertex maps to one binary variable),
41    /// the solution extraction is simply copying the configuration.
42    fn extract_solution(
43        &self,
44        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
45    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
46        crate::rules::traits::validate_target_witness(
47            self.target_problem(),
48            target_solution,
49            |value| value.value.is_some(),
50            "target ILP assignment is infeasible",
51        )?;
52
53        Ok(target_solution.iter().map(|&value| value == 1).collect())
54    }
55}
56
57#[crate::aggregate_reduction(ilp_feasibility)]
58impl crate::rules::AggregateReductionResult for ReductionKCliqueToILP {}
59
60#[reduction(transform = upper_bound {
61    max_constraint_magnitude_bits = "k + 1",
62    num_vars = "num_vertices",
63    num_constraints = "num_vertices^2 + 1",
64    num_nonzeros = "num_vertices * (num_vertices^2 + 1)",
65})]
66impl ReduceTo<ILP<bool>> for KClique<SimpleGraph> {
67    type Result = ReductionKCliqueToILP;
68
69    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
70        let num_vars = self.graph().num_vertices();
71        let k =
72            <Self as ReduceTo<ILP<bool>>>::exact_i64(self.k(), "encoding the clique cardinality")?;
73
74        let mut constraints: Vec<LinearConstraint> = Vec::new();
75
76        // Cardinality constraint: sum of x_v >= k (select at least k vertices)
77        let cardinality_terms: Vec<(usize, i64)> = (0..num_vars).map(|v| (v, 1)).collect();
78        constraints.push(LinearConstraint::ge(cardinality_terms, k));
79
80        // Non-edge constraints: x_u + x_v <= 1 for each non-edge (u, v)
81        // Ensures no two selected vertices are non-adjacent (i.e., selected set is a clique)
82        for u in 0..num_vars {
83            for v in (u + 1)..num_vars {
84                if !self.graph().has_edge(u, v) {
85                    constraints.push(LinearConstraint::le(vec![(u, 1), (v, 1)], 1));
86                }
87            }
88        }
89
90        // Objective: empty (feasibility problem — minimize 0)
91        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
92            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
93
94        Ok(ReductionKCliqueToILP { target })
95    }
96}
97
98#[cfg(feature = "example-db")]
99pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
100    use crate::export::SolutionPair;
101
102    vec![crate::example_db::specs::RuleExampleSpec {
103        id: "kclique_to_ilp",
104        build: || {
105            // K4 (complete graph on 4 vertices), k=3 → feasible (has a 3-clique)
106            let source = KClique::new(
107                SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
108                3,
109            );
110            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
111                source,
112                SolutionPair {
113                    source_config: serde_json::json!(vec![true, true, true, false]),
114                    target_config: serde_json::json!(vec![1, 1, 1, 0]),
115                },
116            )
117        },
118    }]
119}
120
121#[cfg(test)]
122#[path = "../unit_tests/rules/kclique_ilp.rs"]
123mod tests;
problemreductions/rules/kclique_ilp.rs

problemreductions/rules/
kclique_ilp.rs
