problemreductions/models/graph/
minimum_feedback_vertex_set.rs

1//! Feedback Vertex Set problem implementation.
2//!
3//! The Feedback Vertex Set problem asks for a minimum weight subset of vertices
4//! whose removal makes the directed graph acyclic (a DAG).
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::DirectedGraph;
8use crate::traits::Problem;
9use crate::types::{Min, One, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinimumFeedbackVertexSet",
16        display_name: "Minimum Feedback Vertex Set",
17        aliases: &["FVS"],
18        dimensions: &[
19            VariantDimension::new("weight", "i64", &["i64", "One"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Find minimum weight feedback vertex set in a directed graph",
24        fields: MinimumFeedbackVertexSetCreateSpec::<i64>::FIELDS,
25    }
26}
27
28/// The Minimum Feedback Vertex Set problem.
29///
30/// Given a directed graph G = (V, A) and weights w_v for each vertex,
31/// find a subset F ⊆ V such that:
32/// - Removing F from G yields a directed acyclic graph (DAG)
33/// - The total weight Σ_{v ∈ F} w_v is minimized
34///
35/// # Example
36///
37/// ```
38/// use problemreductions::models::graph::MinimumFeedbackVertexSet;
39/// use problemreductions::topology::DirectedGraph;
40/// use problemreductions::{Problem, BruteForce};
41///
42/// // Simple 3-cycle: 0 → 1 → 2 → 0
43/// let graph = DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]);
44/// let problem = MinimumFeedbackVertexSet::new(graph, vec![1; 3]);
45///
46/// let solver = BruteForce::new();
47/// let solutions = solver.find_all_witnesses(&problem).unwrap();
48///
49/// // Any single vertex breaks the cycle
50/// assert_eq!(solutions.len(), 3);
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53#[serde(try_from = "MinimumFeedbackVertexSetData<W>")]
54#[serde(bound(deserialize = "W: Clone + Default + Deserialize<'de>"))]
55pub struct MinimumFeedbackVertexSet<W> {
56    /// The underlying directed graph.
57    graph: DirectedGraph,
58    /// Weights for each vertex.
59    weights: Vec<W>,
60}
61
62#[derive(Deserialize)]
63struct MinimumFeedbackVertexSetData<W> {
64    graph: DirectedGraph,
65    weights: Vec<W>,
66}
67
68impl<W> TryFrom<MinimumFeedbackVertexSetData<W>> for MinimumFeedbackVertexSet<W>
69where
70    W: Clone + Default,
71{
72    type Error = crate::registry::ConstructionError;
73
74    fn try_from(data: MinimumFeedbackVertexSetData<W>) -> Result<Self, Self::Error> {
75        Self::try_new(data.graph, data.weights)
76    }
77}
78
79#[derive(Debug, Deserialize, crate::CreateSpec)]
80struct MinimumFeedbackVertexSetCreateSpec<W> {
81    /// The directed graph.
82    graph: DirectedGraph,
83    /// Vertex weights; defaults to one per vertex.
84    weights: Option<Vec<W>>,
85}
86impl<W: WeightElement> TryFrom<MinimumFeedbackVertexSetCreateSpec<W>>
87    for MinimumFeedbackVertexSet<W>
88{
89    type Error = crate::registry::ConstructionError;
90    fn try_from(spec: MinimumFeedbackVertexSetCreateSpec<W>) -> Result<Self, Self::Error> {
91        let count = spec.graph.num_vertices();
92        let weights = spec.weights.unwrap_or_else(|| vec![W::unit(); count]);
93        Self::try_new(spec.graph, weights)
94    }
95}
96
97impl<W: Clone + Default> MinimumFeedbackVertexSet<W> {
98    /// Create a Feedback Vertex Set problem from a directed graph with given weights.
99    pub fn new(graph: DirectedGraph, weights: Vec<W>) -> Self {
100        Self::try_new(graph, weights).unwrap_or_else(|error| panic!("{error}"))
101    }
102
103    fn try_new(
104        graph: DirectedGraph,
105        weights: Vec<W>,
106    ) -> Result<Self, crate::registry::ConstructionError> {
107        Self::check_weights(&graph, &weights)?;
108        Ok(Self { graph, weights })
109    }
110
111    /// Get a reference to the underlying directed graph.
112    pub fn graph(&self) -> &DirectedGraph {
113        &self.graph
114    }
115
116    /// Get a reference to the weights slice.
117    pub fn weights(&self) -> &[W] {
118        &self.weights
119    }
120
121    /// Set vertex weights.
122    pub fn set_weights(&mut self, weights: Vec<W>) {
123        Self::check_weights(&self.graph, &weights).unwrap_or_else(|error| panic!("{error}"));
124        self.weights = weights;
125    }
126
127    fn check_weights(
128        graph: &DirectedGraph,
129        weights: &[W],
130    ) -> Result<(), crate::registry::ConstructionError> {
131        if weights.len() != graph.num_vertices() {
132            return Err(crate::registry::ConstructionError::length_mismatch(
133                "weights",
134                weights.len(),
135                graph.num_vertices(),
136            ));
137        }
138        Ok(())
139    }
140
141    /// Check if a configuration is a valid feedback vertex set.
142    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
143        if config.len() != self.graph.num_vertices() {
144            return false;
145        }
146        let keep: Vec<bool> = config.iter().map(|&c| c == 0).collect();
147        self.graph.induced_subgraph(&keep).is_dag()
148    }
149}
150
151impl<W: WeightElement> MinimumFeedbackVertexSet<W> {
152    /// Check if the problem has non-unit weights.
153    pub fn is_weighted(&self) -> bool {
154        !W::IS_UNIT
155    }
156
157    /// Get the number of vertices in the underlying directed graph.
158    pub fn num_vertices(&self) -> usize {
159        self.graph.num_vertices()
160    }
161
162    /// Get the number of arcs in the underlying directed graph.
163    pub fn num_arcs(&self) -> usize {
164        self.graph.num_arcs()
165    }
166}
167
168impl<W> Problem for MinimumFeedbackVertexSet<W>
169where
170    W: WeightElement + crate::variant::VariantParam,
171{
172    const NAME: &'static str = "MinimumFeedbackVertexSet";
173    type Solution = Vec<bool>;
174    type Value = Min<W::Sum>;
175
176    crate::problem_parameters![("num_arcs", num_arcs), ("num_vertices", num_vertices),];
177
178    fn variant() -> Vec<(&'static str, &'static str)> {
179        crate::variant_params![W]
180    }
181
182    fn evaluate(
183        &self,
184        config: &Self::Solution,
185    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
186        Ok({
187            if config.len() != self.graph.num_vertices() {
188                return Err(crate::traits::EvaluationError::InvalidConfiguration(
189                    "vertex-selection length does not match the graph".into(),
190                ));
191            }
192            // keep[v] = true if vertex v is NOT selected for removal
193            let keep: Vec<bool> = config.iter().map(|&removed| !removed).collect();
194            let subgraph = self.graph.induced_subgraph(&keep);
195            if !subgraph.is_dag() {
196                return Ok(Min(None));
197            }
198            let mut total = W::Sum::zero();
199            for (i, &selected) in config.iter().enumerate() {
200                if selected {
201                    total = W::checked_add_to_sum(
202                        total,
203                        self.weights[i].to_sum(),
204                        "summing selected feedback-vertex weights",
205                    )?;
206                }
207            }
208            Min(Some(total))
209        })
210    }
211}
212
213impl<W> crate::solvers::BruteForceProblem for MinimumFeedbackVertexSet<W>
214where
215    W: WeightElement + crate::variant::VariantParam,
216{
217    fn dimensions(&self) -> Vec<usize> {
218        vec![2; self.graph.num_vertices()]
219    }
220}
221
222#[derive(Debug, Deserialize, crate::CreateSpec)]
223struct MinimumFeedbackVertexSetOneCreateSpec {
224    /// The underlying graph.
225    graph: DirectedGraph,
226}
227
228impl TryFrom<MinimumFeedbackVertexSetOneCreateSpec> for MinimumFeedbackVertexSet<One> {
229    type Error = crate::registry::ConstructionError;
230    fn try_from(spec: MinimumFeedbackVertexSetOneCreateSpec) -> Result<Self, Self::Error> {
231        let weights = vec![One; spec.graph.num_vertices()];
232        Self::try_new(spec.graph, weights)
233    }
234}
235
236crate::declare_variants! {
237    default MinimumFeedbackVertexSet<i64> => "1.9977^num_vertices" create MinimumFeedbackVertexSetCreateSpec<i64>,
238    MinimumFeedbackVertexSet<One> => "1.9977^num_vertices" create MinimumFeedbackVertexSetOneCreateSpec,
239}
240
241crate::register_brute_force! {
242    MinimumFeedbackVertexSet<i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
243    MinimumFeedbackVertexSet<One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
244}
245
246#[cfg(feature = "example-db")]
247pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
248    use crate::topology::DirectedGraph;
249    vec![
250        crate::example_db::specs::ModelExampleSpec {
251            id: "minimum_feedback_vertex_set",
252            instance: Box::new(MinimumFeedbackVertexSet::new(
253                DirectedGraph::new(
254                    5,
255                    vec![(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 1), (4, 2)],
256                ),
257                vec![1i64; 5],
258            )),
259            optimal_config: serde_json::json!(vec![true, false, false, false, false]),
260            optimal_value: serde_json::json!(1),
261        },
262        crate::example_db::specs::ModelExampleSpec {
263            id: "minimum_feedback_vertex_set_unit",
264            instance: Box::new(MinimumFeedbackVertexSet::new(
265                DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]),
266                vec![One; 3],
267            )),
268            optimal_config: serde_json::json!(vec![true, false, false]),
269            optimal_value: serde_json::json!(1),
270        },
271    ]
272}
273
274/// Check if a set of vertices is a feedback vertex set (removing them makes the graph a DAG).
275///
276/// # Panics
277/// Panics if `selected.len() != graph.num_vertices()`.
278#[cfg(test)]
279pub(crate) fn is_feedback_vertex_set(graph: &DirectedGraph, selected: &[bool]) -> bool {
280    assert_eq!(
281        selected.len(),
282        graph.num_vertices(),
283        "selected length must match num_vertices"
284    );
285    // keep = NOT selected
286    let keep: Vec<bool> = selected.iter().map(|&s| !s).collect();
287    graph.induced_subgraph(&keep).is_dag()
288}
289
290#[cfg(test)]
291#[path = "../../unit_tests/models/graph/minimum_feedback_vertex_set.rs"]
292mod tests;
problemreductions/models/graph/minimum_feedback_vertex_set.rs

problemreductions/models/graph/
minimum_feedback_vertex_set.rs
