problemreductions/rules/
minimumvertexcover_minimumfeedbackvertexset.rs

1//! Reduction from MinimumVertexCover to MinimumFeedbackVertexSet.
2//!
3//! Each undirected edge becomes a directed 2-cycle, so a vertex cover is
4//! exactly a feedback vertex set in the constructed digraph.
5
6use crate::models::graph::{MinimumFeedbackVertexSet, MinimumVertexCover};
7use crate::reduction;
8use crate::rules::traits::{ReduceTo, ReductionResult};
9use crate::topology::{DirectedGraph, Graph, SimpleGraph};
10use crate::types::WeightElement;
11
12/// Result of reducing MinimumVertexCover to MinimumFeedbackVertexSet.
13#[derive(Debug, Clone)]
14pub struct ReductionVCToFVS<W> {
15    target: MinimumFeedbackVertexSet<W>,
16}
17
18impl<W> ReductionResult for ReductionVCToFVS<W>
19where
20    W: WeightElement + crate::variant::VariantParam,
21{
22    type Source = MinimumVertexCover<SimpleGraph, W>;
23    type Target = MinimumFeedbackVertexSet<W>;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
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        num_vertices = "num_vertices",
42        num_arcs = "2 * num_edges",
43    }
44)]
45impl ReduceTo<MinimumFeedbackVertexSet<i64>> for MinimumVertexCover<SimpleGraph, i64> {
46    type Result = ReductionVCToFVS<i64>;
47
48    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
49        let arcs = self
50            .graph()
51            .edges()
52            .into_iter()
53            .flat_map(|(u, v)| [(u, v), (v, u)])
54            .collect();
55
56        let target = MinimumFeedbackVertexSet::new(
57            DirectedGraph::new(self.graph().num_vertices(), arcs),
58            self.weights().to_vec(),
59        );
60
61        Ok(ReductionVCToFVS { target })
62    }
63}
64
65#[cfg(feature = "example-db")]
66pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
67    use crate::export::SolutionPair;
68
69    vec![crate::example_db::specs::RuleExampleSpec {
70        id: "minimumvertexcover_to_minimumfeedbackvertexset",
71        build: || {
72            let source = MinimumVertexCover::new(
73                SimpleGraph::new(
74                    7,
75                    vec![
76                        (0, 1),
77                        (0, 2),
78                        (0, 3),
79                        (1, 2),
80                        (1, 3),
81                        (3, 4),
82                        (4, 5),
83                        (5, 6),
84                    ],
85                ),
86                vec![1i64; 7],
87            );
88
89            crate::example_db::specs::rule_example_with_witness::<_, MinimumFeedbackVertexSet<i64>>(
90                source,
91                SolutionPair {
92                    source_config: serde_json::json!(vec![
93                        true, true, false, true, false, true, false
94                    ]),
95                    target_config: serde_json::json!(vec![
96                        true, true, false, true, false, true, false
97                    ]),
98                },
99            )
100        },
101    }]
102}
103
104#[cfg(test)]
105#[path = "../unit_tests/rules/minimumvertexcover_minimumfeedbackvertexset.rs"]
106mod tests;
problemreductions/rules/minimumvertexcover_minimumfeedbackvertexset.rs

problemreductions/rules/
minimumvertexcover_minimumfeedbackvertexset.rs
