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<i32>,
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, i32>;
26    type Target = MinimumFeedbackArcSet<i32>;
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(&self, target_solution: &[usize]) -> Vec<usize> {
35        target_solution[..self.num_source_vertices].to_vec()
36    }
37}
38
39#[reduction(
40    overhead = {
41        num_vertices = "2 * num_vertices",
42        num_arcs = "num_vertices + 2 * num_edges",
43    }
44)]
45impl ReduceTo<MinimumFeedbackArcSet<i32>> for MinimumVertexCover<SimpleGraph, i32> {
46    type Result = ReductionVCToFAS;
47
48    fn reduce_to(&self) -> Self::Result {
49        let n = self.graph().num_vertices();
50        let edges = self.graph().edges();
51
52        // Vertex splitting: vertex v → v^in (index v) and v^out (index n + v)
53        // Internal arcs: (v^in → v^out) for each vertex v, with weight w(v)
54        // Crossing arcs: for each edge {u,v}, add (u^out → v^in) and (v^out → u^in) with weight M
55
56        let weight_sum: i32 = self.weights().iter().sum::<i32>();
57        let big_m: i32 = weight_sum
58            .checked_add(1)
59            .expect("penalty M = 1 + sum(weights) overflows i32");
60
61        let mut arcs = Vec::with_capacity(n + 2 * edges.len());
62        let mut weights = Vec::with_capacity(n + 2 * edges.len());
63
64        // Internal arcs first (indices 0..n)
65        for v in 0..n {
66            arcs.push((v, n + v)); // v^in → v^out
67            weights.push(self.weights()[v]);
68        }
69
70        // Crossing arcs for each edge
71        for (u, v) in &edges {
72            arcs.push((n + u, *v)); // u^out → v^in
73            weights.push(big_m);
74            arcs.push((n + v, *u)); // v^out → u^in
75            weights.push(big_m);
76        }
77
78        let graph = DirectedGraph::new(2 * n, arcs);
79        let target = MinimumFeedbackArcSet::new(graph, weights);
80
81        ReductionVCToFAS {
82            target,
83            num_source_vertices: n,
84        }
85    }
86}
87
88#[cfg(feature = "example-db")]
89pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
90    use crate::export::SolutionPair;
91    use crate::solvers::BruteForce;
92
93    vec![crate::example_db::specs::RuleExampleSpec {
94        id: "minimumvertexcover_to_minimumfeedbackarcset",
95        build: || {
96            // Triangle graph: 0-1-2-0, unit weights
97            // MVC optimal = 2 vertices (e.g., {0, 1})
98            let source = MinimumVertexCover::new(
99                SimpleGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]),
100                vec![1i32; 3],
101            );
102            let reduction = ReduceTo::<MinimumFeedbackArcSet<i32>>::reduce_to(&source);
103            let target = reduction.target_problem();
104
105            let target_witness = BruteForce::new()
106                .find_witness(target)
107                .expect("target should have an optimum");
108            let source_witness = reduction.extract_solution(&target_witness);
109
110            crate::example_db::specs::rule_example_with_witness::<_, MinimumFeedbackArcSet<i32>>(
111                source,
112                SolutionPair {
113                    source_config: source_witness,
114                    target_config: target_witness,
115                },
116            )
117        },
118    }]
119}
120
121#[cfg(test)]
122#[path = "../unit_tests/rules/minimumvertexcover_minimumfeedbackarcset.rs"]
123mod tests;
problemreductions/rules/minimumvertexcover_minimumfeedbackarcset.rs

problemreductions/rules/
minimumvertexcover_minimumfeedbackarcset.rs
