problemreductions/rules/
minimumvertexcover_minimumhittingset.rs

1//! Reduction from MinimumVertexCover (unit-weight) to MinimumHittingSet.
2//!
3//! Each edge becomes a 2-element subset and vertices become universe elements.
4//! A vertex cover of G is exactly a hitting set for the edge-subset collection.
5
6use crate::models::graph::MinimumVertexCover;
7use crate::models::set::MinimumHittingSet;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::types::One;
12
13/// Result of reducing MinimumVertexCover<SimpleGraph, One> to MinimumHittingSet.
14#[derive(Debug, Clone)]
15pub struct ReductionVCToHS {
16    target: MinimumHittingSet,
17}
18
19impl ReductionResult for ReductionVCToHS {
20    type Source = MinimumVertexCover<SimpleGraph, One>;
21    type Target = MinimumHittingSet;
22
23    fn target_problem(&self) -> &Self::Target {
24        &self.target
25    }
26
27    /// Solution extraction: variables correspond 1:1.
28    /// Element i in the hitting set corresponds to vertex i in the vertex cover.
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
34
35        Ok(target_solution.to_vec())
36    }
37}
38
39#[reduction(
40    transform = exact {
41        universe_size = "num_vertices",
42        num_sets = "num_edges",
43    }
44)]
45impl ReduceTo<MinimumHittingSet> for MinimumVertexCover<SimpleGraph, One> {
46    type Result = ReductionVCToHS;
47
48    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
49        let edges = self.graph().edges();
50        let num_vertices = self.graph().num_vertices();
51
52        // For each edge (u, v), create a 2-element subset {u, v}.
53        let sets: Vec<Vec<usize>> = edges.iter().map(|&(u, v)| vec![u, v]).collect();
54
55        let target = MinimumHittingSet::new(num_vertices, sets);
56
57        Ok(ReductionVCToHS { target })
58    }
59}
60
61#[cfg(feature = "example-db")]
62pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
63    use crate::export::SolutionPair;
64
65    vec![crate::example_db::specs::RuleExampleSpec {
66        id: "minimumvertexcover_to_minimumhittingset",
67        build: || {
68            // 6-vertex graph from the issue example
69            let source = MinimumVertexCover::new(
70                SimpleGraph::new(
71                    6,
72                    vec![
73                        (0, 1),
74                        (0, 2),
75                        (1, 3),
76                        (2, 3),
77                        (2, 4),
78                        (3, 5),
79                        (4, 5),
80                        (1, 4),
81                    ],
82                ),
83                vec![One; 6],
84            );
85            crate::example_db::specs::rule_example_with_witness::<_, MinimumHittingSet>(
86                source,
87                SolutionPair {
88                    source_config: serde_json::json!(vec![true, false, false, true, true, false]),
89                    target_config: serde_json::json!(vec![true, false, false, true, true, false]),
90                },
91            )
92        },
93    }]
94}
95
96#[cfg(test)]
97#[path = "../unit_tests/rules/minimumvertexcover_minimumhittingset.rs"]
98mod tests;
problemreductions/rules/minimumvertexcover_minimumhittingset.rs

problemreductions/rules/
minimumvertexcover_minimumhittingset.rs
