problemreductions/rules/
minimumvertexcover_minimumfeedbackarcset.rs

1//! Reduction from MinimumVertexCover to MinimumFeedbackArcSet.
2//!
3//! Each vertex v is split into v^in and v^out connected by an internal arc
4//! (v^in → v^out) with weight w(v). For each edge {u,v}, two crossing arcs
5//! (u^out → v^in) and (v^out → u^in) are added with a large penalty weight
6//! M = 1 + Σ w(v). The penalty ensures no optimal FAS includes crossing arcs.
7//!
8//! A vertex cover of the source maps to a feedback arc set of internal arcs:
9//! if vertex i is in the cover, remove internal arc i.
10
11use crate::models::graph::{MinimumFeedbackArcSet, MinimumVertexCover};
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14use crate::topology::{DirectedGraph, Graph, SimpleGraph};
15
16/// Result of reducing MinimumVertexCover to MinimumFeedbackArcSet.
17#[derive(Debug, Clone)]
18pub struct ReductionVCToFAS {
19    target: MinimumFeedbackArcSet<i64>,
20    /// Number of vertices in the source graph (= number of internal arcs).
21    num_source_vertices: usize,
22}
23
24impl ReductionResult for ReductionVCToFAS {
25    type Source = MinimumVertexCover<SimpleGraph, i64>;
26    type Target = MinimumFeedbackArcSet<i64>;
27
28    fn target_problem(&self) -> &Self::Target {
29        &self.target
30    }
31
32    /// Extract solution: internal arcs are at positions 0..n in the FAS config.
33    /// If internal arc i is in the FAS (config[i] = 1), vertex i is in the cover.
34    fn extract_solution(
35        &self,
36        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
37    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
38        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
39
40        Ok(target_solution[..self.num_source_vertices].to_vec())
41    }
42}
43
44#[reduction(
45    transform = exact {
46        num_vertices = "2 * num_vertices",
47        num_arcs = "num_vertices + 2 * num_edges",
48    }
49)]
50impl ReduceTo<MinimumFeedbackArcSet<i64>> for MinimumVertexCover<SimpleGraph, i64> {
51    type Result = ReductionVCToFAS;
52
53    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
54        let n = self.graph().num_vertices();
55        let edges = self.graph().edges();
56
57        // Vertex splitting: vertex v → v^in (index v) and v^out (index n + v)
58        // Internal arcs: (v^in → v^out) for each vertex v, with weight w(v)
59        // Crossing arcs: for each edge {u,v}, add (u^out → v^in) and (v^out → u^in) with weight M
60
61        let weight_sum = self.weights().iter().try_fold(0i64, |sum, &weight| {
62            sum.checked_add(weight).ok_or_else(|| {
63                crate::rules::ReductionError::integer_overflow::<
64                    MinimumVertexCover<SimpleGraph, i64>,
65                    MinimumFeedbackArcSet<i64>,
66                >("summing source vertex weights")
67            })
68        })?;
69        let big_m = weight_sum.checked_add(1).ok_or_else(|| {
70            crate::rules::ReductionError::integer_overflow::<
71                MinimumVertexCover<SimpleGraph, i64>,
72                MinimumFeedbackArcSet<i64>,
73            >("computing the crossing-arc penalty")
74        })?;
75
76        let mut arcs = Vec::with_capacity(n + 2 * edges.len());
77        let mut weights = Vec::with_capacity(n + 2 * edges.len());
78
79        // Internal arcs first (indices 0..n)
80        for v in 0..n {
81            arcs.push((v, n + v)); // v^in → v^out
82            weights.push(self.weights()[v]);
83        }
84
85        // Crossing arcs for each edge
86        for (u, v) in &edges {
87            arcs.push((n + u, *v)); // u^out → v^in
88            weights.push(big_m);
89            arcs.push((n + v, *u)); // v^out → u^in
90            weights.push(big_m);
91        }
92
93        let graph = DirectedGraph::new(2 * n, arcs);
94        let target = MinimumFeedbackArcSet::new(graph, weights);
95
96        Ok(ReductionVCToFAS {
97            target,
98            num_source_vertices: n,
99        })
100    }
101}
102
103#[cfg(feature = "example-db")]
104pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
105    use crate::export::SolutionPair;
106    use crate::solvers::BruteForce;
107
108    vec![crate::example_db::specs::RuleExampleSpec {
109        id: "minimumvertexcover_to_minimumfeedbackarcset",
110        build: || {
111            // Triangle graph: 0-1-2-0, unit weights
112            // MVC optimal = 2 vertices (e.g., {0, 1})
113            let source = MinimumVertexCover::new(
114                SimpleGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]),
115                vec![1i64; 3],
116            );
117            let reduction = ReduceTo::<MinimumFeedbackArcSet<i64>>::reduce_to(&source)
118                .expect("reduction should succeed");
119            let target = reduction.target_problem();
120
121            let target_witness = BruteForce::new()
122                .solve(target)
123                .expect("target evaluation should succeed")
124                .expect("target should have an optimum");
125            let source_witness = reduction.extract_solution(&target_witness).unwrap();
126
127            crate::example_db::specs::rule_example_with_witness::<_, MinimumFeedbackArcSet<i64>>(
128                source,
129                SolutionPair {
130                    source_config: serde_json::json!(source_witness),
131                    target_config: serde_json::json!(target_witness),
132                },
133            )
134        },
135    }]
136}
137
138#[cfg(test)]
139#[path = "../unit_tests/rules/minimumvertexcover_minimumfeedbackarcset.rs"]
140mod tests;
problemreductions/rules/minimumvertexcover_minimumfeedbackarcset.rs

problemreductions/rules/
minimumvertexcover_minimumfeedbackarcset.rs
