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

problemreductions/rules/
minimumvertexcover_minimumfeedbackarcset.rs
