problemreductions/rules/
maximumindependentset_maximumsetpacking.rs

1//! Reductions between MaximumIndependentSet and MaximumSetPacking problems.
2//!
3//! IS → MaximumSetPacking: Each vertex becomes a set containing its incident edge indices.
4//! MaximumSetPacking → IS: Each set becomes a vertex; two vertices are adjacent if their sets overlap.
5
6use crate::models::graph::MaximumIndependentSet;
7use crate::models::set::MaximumSetPacking;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::types::{One, WeightElement};
12use std::collections::HashSet;
13
14/// Result of reducing MaximumIndependentSet to MaximumSetPacking.
15#[derive(Debug, Clone)]
16pub struct ReductionISToSP<W> {
17    target: MaximumSetPacking<W>,
18}
19
20impl<W> ReductionResult for ReductionISToSP<W>
21where
22    W: WeightElement + crate::variant::VariantParam,
23{
24    type Source = MaximumIndependentSet<SimpleGraph, W>;
25    type Target = MaximumSetPacking<W>;
26
27    fn target_problem(&self) -> &Self::Target {
28        &self.target
29    }
30
31    /// Solutions map directly: vertex selection = set selection.
32    fn extract_solution(
33        &self,
34        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
35    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
36        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
37
38        Ok(target_solution.to_vec())
39    }
40}
41
42macro_rules! impl_is_to_sp {
43    ($W:ty) => {
44        #[reduction(transform = upper_bound { num_sets = "num_vertices", universe_size = "num_edges" })]
45        impl ReduceTo<MaximumSetPacking<$W>> for MaximumIndependentSet<SimpleGraph, $W> {
46            type Result = ReductionISToSP<$W>;
47
48            fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
49                let edges = self.graph().edges();
50                let n = self.graph().num_vertices();
51
52                // For each vertex, collect the indices of its incident edges
53                let mut sets: Vec<Vec<usize>> = vec![Vec::new(); n];
54                for (edge_idx, &(u, v)) in edges.iter().enumerate() {
55                    sets[u].push(edge_idx);
56                    sets[v].push(edge_idx);
57                }
58
59                let target = MaximumSetPacking::with_weights(sets, self.weights().to_vec())
60                    .map_err(|cause| {
61                        crate::rules::ReductionError::construction::<
62                            MaximumIndependentSet<SimpleGraph, $W>,
63                            MaximumSetPacking<$W>,
64                        >(cause)
65                    })?;
66
67                Ok(ReductionISToSP { target })
68            }
69        }
70    };
71}
72
73impl_is_to_sp!(i64);
74impl_is_to_sp!(One);
75
76/// Result of reducing MaximumSetPacking to MaximumIndependentSet.
77#[derive(Debug, Clone)]
78pub struct ReductionSPToIS<W> {
79    target: MaximumIndependentSet<SimpleGraph, W>,
80}
81
82impl<W> ReductionResult for ReductionSPToIS<W>
83where
84    W: WeightElement + crate::variant::VariantParam,
85{
86    type Source = MaximumSetPacking<W>;
87    type Target = MaximumIndependentSet<SimpleGraph, W>;
88
89    fn target_problem(&self) -> &Self::Target {
90        &self.target
91    }
92
93    /// Solutions map directly.
94    fn extract_solution(
95        &self,
96        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
97    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
98        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
99
100        Ok(target_solution.to_vec())
101    }
102}
103
104macro_rules! impl_sp_to_is {
105    ($W:ty) => {
106        #[reduction(transform = upper_bound { num_vertices = "num_sets", num_edges = "num_sets^2" })]
107        impl ReduceTo<MaximumIndependentSet<SimpleGraph, $W>> for MaximumSetPacking<$W> {
108            type Result = ReductionSPToIS<$W>;
109
110            fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
111                let sets = self.sets();
112                let n = sets.len();
113
114                // Create edges between sets that overlap
115                let mut edges = Vec::new();
116                for (i, set_i_vec) in sets.iter().enumerate() {
117                    let set_i: HashSet<_> = set_i_vec.iter().collect();
118                    for (j, set_j) in sets.iter().enumerate().skip(i + 1) {
119                        // Check if sets[i] and sets[j] overlap
120                        if set_j.iter().any(|elem| set_i.contains(elem)) {
121                            edges.push((i, j));
122                        }
123                    }
124                }
125
126                let target = MaximumIndependentSet::new(
127                    SimpleGraph::new(n, edges),
128                    self.weights_ref().clone(),
129                );
130
131                Ok(ReductionSPToIS { target })
132            }
133        }
134    };
135}
136
137impl_sp_to_is!(i64);
138impl_sp_to_is!(One);
139
140#[cfg(feature = "example-db")]
141pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
142    use crate::export::SolutionPair;
143
144    vec![
145        crate::example_db::specs::RuleExampleSpec {
146            id: "weighted_maximumindependentset_to_maximumsetpacking",
147            build: || {
148                let (n, edges) = crate::topology::small_graphs::petersen();
149                let source = MaximumIndependentSet::new(SimpleGraph::new(n, edges), vec![1i64; 10]);
150                crate::example_db::specs::rule_example_with_witness::<_, MaximumSetPacking<i64>>(
151                    source,
152                    SolutionPair {
153                        source_config: serde_json::json!(vec![
154                            true, false, false, true, false, false, true, true, false, false
155                        ]),
156                        target_config: serde_json::json!(vec![
157                            true, false, false, true, false, false, true, true, false, false
158                        ]),
159                    },
160                )
161            },
162        },
163        crate::example_db::specs::RuleExampleSpec {
164            id: "cardinality_maximumindependentset_to_maximumsetpacking",
165            build: || {
166                let (n, edges) = crate::topology::small_graphs::petersen();
167                let source = MaximumIndependentSet::new(SimpleGraph::new(n, edges), vec![One; 10]);
168                crate::example_db::specs::rule_example_with_witness::<_, MaximumSetPacking<One>>(
169                    source,
170                    SolutionPair {
171                        source_config: serde_json::json!(vec![
172                            true, false, false, true, false, false, true, true, false, false
173                        ]),
174                        target_config: serde_json::json!(vec![
175                            true, false, false, true, false, false, true, true, false, false
176                        ]),
177                    },
178                )
179            },
180        },
181        crate::example_db::specs::RuleExampleSpec {
182            id: "weighted_maximumsetpacking_to_maximumindependentset",
183            build: || {
184                let sets = vec![
185                    vec![0, 1, 2],
186                    vec![2, 3],
187                    vec![4, 5, 6],
188                    vec![1, 5, 7],
189                    vec![3, 6],
190                ];
191                let source = MaximumSetPacking::with_weights(sets, vec![1i64; 5]).unwrap();
192                crate::example_db::specs::rule_example_with_witness::<
193                    _,
194                    MaximumIndependentSet<SimpleGraph, i64>,
195                >(
196                    source,
197                    SolutionPair {
198                        source_config: serde_json::json!(vec![true, false, false, false, true]),
199                        target_config: serde_json::json!(vec![true, false, false, false, true]),
200                    },
201                )
202            },
203        },
204        crate::example_db::specs::RuleExampleSpec {
205            id: "cardinality_maximumsetpacking_to_maximumindependentset",
206            build: || {
207                let sets = vec![
208                    vec![0, 1, 2],
209                    vec![2, 3],
210                    vec![4, 5, 6],
211                    vec![1, 5, 7],
212                    vec![3, 6],
213                ];
214                let source = MaximumSetPacking::with_weights(sets, vec![One; 5]).unwrap();
215                crate::example_db::specs::rule_example_with_witness::<
216                    _,
217                    MaximumIndependentSet<SimpleGraph, One>,
218                >(
219                    source,
220                    SolutionPair {
221                        source_config: serde_json::json!(vec![true, false, false, false, true]),
222                        target_config: serde_json::json!(vec![true, false, false, false, true]),
223                    },
224                )
225            },
226        },
227    ]
228}
229
230#[cfg(test)]
231#[path = "../unit_tests/rules/maximumindependentset_maximumsetpacking.rs"]
232mod tests;
problemreductions/rules/maximumindependentset_maximumsetpacking.rs

problemreductions/rules/
maximumindependentset_maximumsetpacking.rs
