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(&self, target_solution: &[usize]) -> Vec<usize> {
43        target_solution.to_vec()
44    }
45}
46
47#[reduction(
48    overhead = {
49        num_vars = "num_vertices",
50        num_constraints = "num_vertices^2",
51    }
52)]
53impl ReduceTo<ILP<bool>> for KClique<SimpleGraph> {
54    type Result = ReductionKCliqueToILP;
55
56    fn reduce_to(&self) -> Self::Result {
57        let num_vars = self.graph().num_vertices();
58        let k = self.k();
59
60        let mut constraints: Vec<LinearConstraint> = Vec::new();
61
62        // Cardinality constraint: sum of x_v >= k (select at least k vertices)
63        let cardinality_terms: Vec<(usize, f64)> = (0..num_vars).map(|v| (v, 1.0)).collect();
64        constraints.push(LinearConstraint::ge(cardinality_terms, k as f64));
65
66        // Non-edge constraints: x_u + x_v <= 1 for each non-edge (u, v)
67        // Ensures no two selected vertices are non-adjacent (i.e., selected set is a clique)
68        for u in 0..num_vars {
69            for v in (u + 1)..num_vars {
70                if !self.graph().has_edge(u, v) {
71                    constraints.push(LinearConstraint::le(vec![(u, 1.0), (v, 1.0)], 1.0));
72                }
73            }
74        }
75
76        // Objective: empty (feasibility problem — minimize 0)
77        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
78
79        ReductionKCliqueToILP { target }
80    }
81}
82
83#[cfg(feature = "example-db")]
84pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
85    use crate::export::SolutionPair;
86
87    vec![crate::example_db::specs::RuleExampleSpec {
88        id: "kclique_to_ilp",
89        build: || {
90            // K4 (complete graph on 4 vertices), k=3 → feasible (has a 3-clique)
91            let source = KClique::new(
92                SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
93                3,
94            );
95            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
96                source,
97                SolutionPair {
98                    source_config: vec![1, 1, 1, 0],
99                    target_config: vec![1, 1, 1, 0],
100                },
101            )
102        },
103    }]
104}
105
106#[cfg(test)]
107#[path = "../unit_tests/rules/kclique_ilp.rs"]
108mod tests;
problemreductions/rules/kclique_ilp.rs

problemreductions/rules/
kclique_ilp.rs
