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(&self, target_solution: &[usize]) -> Vec<usize> {
30        target_solution.to_vec()
31    }
32}
33
34#[reduction(
35    overhead = {
36        universe_size = "num_vertices",
37        num_sets = "num_edges",
38    }
39)]
40impl ReduceTo<MinimumHittingSet> for MinimumVertexCover<SimpleGraph, One> {
41    type Result = ReductionVCToHS;
42
43    fn reduce_to(&self) -> Self::Result {
44        let edges = self.graph().edges();
45        let num_vertices = self.graph().num_vertices();
46
47        // For each edge (u, v), create a 2-element subset {u, v}.
48        let sets: Vec<Vec<usize>> = edges.iter().map(|&(u, v)| vec![u, v]).collect();
49
50        let target = MinimumHittingSet::new(num_vertices, sets);
51
52        ReductionVCToHS { target }
53    }
54}
55
56#[cfg(feature = "example-db")]
57pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
58    use crate::export::SolutionPair;
59
60    vec![crate::example_db::specs::RuleExampleSpec {
61        id: "minimumvertexcover_to_minimumhittingset",
62        build: || {
63            // 6-vertex graph from the issue example
64            let source = MinimumVertexCover::new(
65                SimpleGraph::new(
66                    6,
67                    vec![
68                        (0, 1),
69                        (0, 2),
70                        (1, 3),
71                        (2, 3),
72                        (2, 4),
73                        (3, 5),
74                        (4, 5),
75                        (1, 4),
76                    ],
77                ),
78                vec![One; 6],
79            );
80            crate::example_db::specs::rule_example_with_witness::<_, MinimumHittingSet>(
81                source,
82                SolutionPair {
83                    source_config: vec![1, 0, 0, 1, 1, 0],
84                    target_config: vec![1, 0, 0, 1, 1, 0],
85                },
86            )
87        },
88    }]
89}
90
91#[cfg(test)]
92#[path = "../unit_tests/rules/minimumvertexcover_minimumhittingset.rs"]
93mod tests;
problemreductions/rules/minimumvertexcover_minimumhittingset.rs

problemreductions/rules/
minimumvertexcover_minimumhittingset.rs
