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(&self, target_solution: &[usize]) -> Vec<usize> {
33        target_solution.to_vec()
34    }
35}
36
37macro_rules! impl_is_to_sp {
38    ($W:ty) => {
39        #[reduction(overhead = { num_sets = "num_vertices", universe_size = "num_edges" })]
40        impl ReduceTo<MaximumSetPacking<$W>> for MaximumIndependentSet<SimpleGraph, $W> {
41            type Result = ReductionISToSP<$W>;
42
43            fn reduce_to(&self) -> Self::Result {
44                let edges = self.graph().edges();
45                let n = self.graph().num_vertices();
46
47                // For each vertex, collect the indices of its incident edges
48                let mut sets: Vec<Vec<usize>> = vec![Vec::new(); n];
49                for (edge_idx, &(u, v)) in edges.iter().enumerate() {
50                    sets[u].push(edge_idx);
51                    sets[v].push(edge_idx);
52                }
53
54                let target = MaximumSetPacking::with_weights(sets, self.weights().to_vec());
55
56                ReductionISToSP { target }
57            }
58        }
59    };
60}
61
62impl_is_to_sp!(i32);
63impl_is_to_sp!(One);
64
65/// Result of reducing MaximumSetPacking to MaximumIndependentSet.
66#[derive(Debug, Clone)]
67pub struct ReductionSPToIS<W> {
68    target: MaximumIndependentSet<SimpleGraph, W>,
69}
70
71impl<W> ReductionResult for ReductionSPToIS<W>
72where
73    W: WeightElement + crate::variant::VariantParam,
74{
75    type Source = MaximumSetPacking<W>;
76    type Target = MaximumIndependentSet<SimpleGraph, W>;
77
78    fn target_problem(&self) -> &Self::Target {
79        &self.target
80    }
81
82    /// Solutions map directly.
83    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
84        target_solution.to_vec()
85    }
86}
87
88macro_rules! impl_sp_to_is {
89    ($W:ty) => {
90        #[reduction(overhead = { num_vertices = "num_sets", num_edges = "num_sets^2" })]
91        impl ReduceTo<MaximumIndependentSet<SimpleGraph, $W>> for MaximumSetPacking<$W> {
92            type Result = ReductionSPToIS<$W>;
93
94            fn reduce_to(&self) -> Self::Result {
95                let sets = self.sets();
96                let n = sets.len();
97
98                // Create edges between sets that overlap
99                let mut edges = Vec::new();
100                for (i, set_i_vec) in sets.iter().enumerate() {
101                    let set_i: HashSet<_> = set_i_vec.iter().collect();
102                    for (j, set_j) in sets.iter().enumerate().skip(i + 1) {
103                        // Check if sets[i] and sets[j] overlap
104                        if set_j.iter().any(|elem| set_i.contains(elem)) {
105                            edges.push((i, j));
106                        }
107                    }
108                }
109
110                let target = MaximumIndependentSet::new(
111                    SimpleGraph::new(n, edges),
112                    self.weights_ref().clone(),
113                );
114
115                ReductionSPToIS { target }
116            }
117        }
118    };
119}
120
121impl_sp_to_is!(i32);
122impl_sp_to_is!(One);
123
124#[cfg(test)]
125#[path = "../unit_tests/rules/maximumindependentset_maximumsetpacking.rs"]
126mod tests;
problemreductions/rules/maximumindependentset_maximumsetpacking.rs

problemreductions/rules/
maximumindependentset_maximumsetpacking.rs
