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

problemreductions/rules/
minimumvertexcover_minimumfeedbackvertexset.rs
