problemreductions/rules/
minimumvertexcover_minimumsetcovering.rs

1//! Reduction from MinimumVertexCover to MinimumSetCovering.
2//!
3//! Each vertex becomes a set containing the edges it covers.
4//! The universe is the set of all edges (labeled 0 to num_edges-1).
5
6use crate::models::graph::MinimumVertexCover;
7use crate::models::set::MinimumSetCovering;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::types::WeightElement;
12
13/// Result of reducing MinimumVertexCover to MinimumSetCovering.
14#[derive(Debug, Clone)]
15pub struct ReductionVCToSC<W> {
16    target: MinimumSetCovering<W>,
17}
18
19impl<W> ReductionResult for ReductionVCToSC<W>
20where
21    W: WeightElement + crate::variant::VariantParam,
22{
23    type Source = MinimumVertexCover<SimpleGraph, W>;
24    type Target = MinimumSetCovering<W>;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    /// Solution extraction: variables correspond 1:1.
31    /// Vertex i in VC corresponds to set i in SC.
32    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
33        target_solution.to_vec()
34    }
35}
36
37#[reduction(
38    overhead = {
39        num_sets = "num_vertices",
40        universe_size = "num_edges",
41    }
42)]
43impl ReduceTo<MinimumSetCovering<i32>> for MinimumVertexCover<SimpleGraph, i32> {
44    type Result = ReductionVCToSC<i32>;
45
46    fn reduce_to(&self) -> Self::Result {
47        let edges = self.graph().edges();
48        let num_edges = edges.len();
49        let num_vertices = self.graph().num_vertices();
50
51        // For each vertex, create a set of edge indices that it covers.
52        // An edge (u, v) with index i is covered by vertex j if j == u or j == v.
53        let sets: Vec<Vec<usize>> = (0..num_vertices)
54            .map(|vertex| {
55                edges
56                    .iter()
57                    .enumerate()
58                    .filter(|(_, (u, v))| *u == vertex || *v == vertex)
59                    .map(|(edge_idx, _)| edge_idx)
60                    .collect()
61            })
62            .collect();
63
64        let target = MinimumSetCovering::with_weights(num_edges, sets, self.weights().to_vec());
65
66        ReductionVCToSC { target }
67    }
68}
69
70#[cfg(feature = "example-db")]
71pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
72    use crate::export::SolutionPair;
73
74    vec![crate::example_db::specs::RuleExampleSpec {
75        id: "minimumvertexcover_to_minimumsetcovering",
76        build: || {
77            let (n, edges) = crate::topology::small_graphs::petersen();
78            let source = MinimumVertexCover::new(SimpleGraph::new(n, edges), vec![1i32; 10]);
79            crate::example_db::specs::rule_example_with_witness::<_, MinimumSetCovering<i32>>(
80                source,
81                SolutionPair {
82                    source_config: vec![0, 1, 1, 0, 1, 1, 0, 0, 1, 1],
83                    target_config: vec![0, 1, 1, 0, 1, 1, 0, 0, 1, 1],
84                },
85            )
86        },
87    }]
88}
89
90#[cfg(test)]
91#[path = "../unit_tests/rules/minimumvertexcover_minimumsetcovering.rs"]
92mod tests;
problemreductions/rules/minimumvertexcover_minimumsetcovering.rs

problemreductions/rules/
minimumvertexcover_minimumsetcovering.rs
