problemreductions/rules/
monochromatictriangle_ilp.rs

1//! Reduction from MonochromaticTriangle to ILP.
2//!
3//! Use one binary variable per edge color. Every triangle must use both colors,
4//! encoded as the pair of inequalities `1 <= sum <= 2` over its three incident
5//! edge variables.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::MonochromaticTriangle;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12use std::collections::HashMap;
13
14/// Result of reducing MonochromaticTriangle to ILP.
15#[derive(Debug, Clone)]
16pub struct ReductionMonochromaticTriangleToILP {
17    target: ILP<bool>,
18}
19
20impl ReductionResult for ReductionMonochromaticTriangleToILP {
21    type Source = MonochromaticTriangle<SimpleGraph>;
22    type Target = ILP<bool>;
23
24    fn target_problem(&self) -> &Self::Target {
25        &self.target
26    }
27
28    fn extract_solution(
29        &self,
30        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
31    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
32        crate::rules::traits::validate_target_witness(
33            self.target_problem(),
34            target_solution,
35            |value| value.value.is_some(),
36            "target ILP assignment is infeasible",
37        )?;
38
39        Ok(target_solution.iter().map(|&value| value == 1).collect())
40    }
41}
42
43#[crate::aggregate_reduction(ilp_feasibility)]
44impl crate::rules::AggregateReductionResult for ReductionMonochromaticTriangleToILP {}
45
46// For T triangles, K five-cliques, and H triangles in a five-clique:
47// rows=2T+15K-H and terms=6T+40K-2H. Incidence counting gives
48// 10K<=T(n-3)(n-4)/2; n<3 implies T=0. This is a direct-source bound;
49// bounded substitution uses the existing positive polynomial hull, dropping
50// negative terms; composed predictions can therefore be looser.
51#[reduction(transform = upper_bound {
52    max_constraint_magnitude_bits = "2",
53    num_vars = "num_edges",
54    num_constraints = "2 * num_triangles + 3 * num_triangles * (num_vertices - 3) * (num_vertices - 4) / 4",
55    num_nonzeros = "6 * num_triangles + 2 * num_triangles * (num_vertices - 3) * (num_vertices - 4)",
56})]
57impl ReduceTo<ILP<bool>> for MonochromaticTriangle<SimpleGraph> {
58    type Result = ReductionMonochromaticTriangleToILP;
59
60    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
61        let mut constraints = Vec::with_capacity(2 * self.num_triangles());
62        for triangle in self.triangles() {
63            let terms: Vec<(usize, i64)> = triangle.iter().map(|&edge_idx| (edge_idx, 1)).collect();
64            constraints.push(LinearConstraint::ge(terms.clone(), 1));
65            constraints.push(LinearConstraint::le(terms, 2));
66        }
67
68        // Every triangle-free two-colouring of K5 consists of two C5s.
69        // Hence each vertex has exactly two incident colour-1 edges in every
70        // K5. These valid equalities strengthen the LP relaxation for all
71        // inputs, independently of how a graph was constructed.
72        let graph = self.graph();
73        let edge_list = self.edge_list();
74        let edge_indices: HashMap<_, _> = edge_list
75            .iter()
76            .enumerate()
77            .map(|(index, &(u, v))| ((u.min(v), u.max(v)), index))
78            .collect();
79        for triangle in self.triangles() {
80            let mut vertices: Vec<_> = triangle
81                .iter()
82                .flat_map(|&edge| [edge_list[edge].0, edge_list[edge].1])
83                .collect();
84            vertices.sort_unstable();
85            vertices.dedup();
86            let [a, b, c] = [vertices[0], vertices[1], vertices[2]];
87            let mut common: Vec<_> = graph
88                .neighbors(c)
89                .into_iter()
90                .filter(|&v| !vertices.contains(&v) && graph.has_edge(a, v) && graph.has_edge(b, v))
91                .collect();
92            common.sort_unstable();
93            common.dedup();
94            // In a K5, the edge opposite this triangle has its majority
95            // colour. All such opposite edges therefore have equal colours.
96            // State these consequences directly so presolve can substitute
97            // colour copies instead of rediscovering the implication by MIP.
98            let mut first_opposite = None;
99            for (index, &d) in common.iter().enumerate() {
100                for &e in &common[index + 1..] {
101                    if graph.has_edge(d, e) {
102                        let opposite = edge_indices[&(d, e)];
103                        if let Some(first) = first_opposite {
104                            constraints
105                                .push(LinearConstraint::eq(vec![(first, 1), (opposite, -1)], 0));
106                        } else {
107                            first_opposite = Some(opposite);
108                        }
109                        // Count each K5's degree equalities only once, using
110                        // its three smallest vertices as the base triangle.
111                        if d <= c {
112                            continue;
113                        }
114                        let clique = [a, b, c, d, e];
115                        for &u in &clique {
116                            let terms = clique
117                                .iter()
118                                .filter(|&&v| v != u)
119                                .map(|&v| (edge_indices[&(u.min(v), u.max(v))], 1))
120                                .collect();
121                            constraints.push(LinearConstraint::eq(terms, 2));
122                        }
123                    }
124                }
125            }
126        }
127
128        Ok(ReductionMonochromaticTriangleToILP {
129            target: ILP::new(
130                self.num_edges(),
131                constraints,
132                vec![],
133                ObjectiveSense::Minimize,
134            )
135            .map_err(Self::target_construction)?,
136        })
137    }
138}
139
140#[cfg(feature = "example-db")]
141pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
142    use crate::topology::SimpleGraph;
143
144    vec![crate::example_db::specs::RuleExampleSpec {
145        id: "monochromatictriangle_to_ilp",
146        build: || {
147            let source = MonochromaticTriangle::new(SimpleGraph::new(
148                4,
149                vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
150            ));
151            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
152        },
153    }]
154}
155
156#[cfg(test)]
157#[path = "../unit_tests/rules/monochromatictriangle_ilp.rs"]
158mod tests;
problemreductions/rules/monochromatictriangle_ilp.rs

problemreductions/rules/
monochromatictriangle_ilp.rs
