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)]
53pub struct MinimumFeedbackVertexSet<W> {
54    /// The underlying directed graph.
55    graph: DirectedGraph,
56    /// Weights for each vertex.
57    weights: Vec<W>,
58}
59
60#[derive(Debug, Deserialize, crate::CreateSpec)]
61struct MinimumFeedbackVertexSetCreateSpec<W> {
62    /// The directed graph.
63    graph: DirectedGraph,
64    /// Vertex weights; defaults to one per vertex.
65    weights: Option<Vec<W>>,
66}
67impl<W: WeightElement> TryFrom<MinimumFeedbackVertexSetCreateSpec<W>>
68    for MinimumFeedbackVertexSet<W>
69{
70    type Error = crate::registry::ConstructionError;
71    fn try_from(spec: MinimumFeedbackVertexSetCreateSpec<W>) -> Result<Self, Self::Error> {
72        let count = spec.graph.num_vertices();
73        let weights = spec.weights.unwrap_or_else(|| vec![W::unit(); count]);
74        if weights.len() != count {
75            return Err(format!("weights has {} entries, expected {count}", weights.len()).into());
76        }
77        Ok(Self::new(spec.graph, weights))
78    }
79}
80
81impl<W: Clone + Default> MinimumFeedbackVertexSet<W> {
82    /// Create a Feedback Vertex Set problem from a directed graph with given weights.
83    pub fn new(graph: DirectedGraph, weights: Vec<W>) -> Self {
84        assert_eq!(
85            weights.len(),
86            graph.num_vertices(),
87            "weights length must match graph num_vertices"
88        );
89        Self { graph, weights }
90    }
91
92    /// Get a reference to the underlying directed graph.
93    pub fn graph(&self) -> &DirectedGraph {
94        &self.graph
95    }
96
97    /// Get a reference to the weights slice.
98    pub fn weights(&self) -> &[W] {
99        &self.weights
100    }
101
102    /// Set vertex weights.
103    pub fn set_weights(&mut self, weights: Vec<W>) {
104        assert_eq!(
105            weights.len(),
106            self.graph.num_vertices(),
107            "weights length must match graph num_vertices"
108        );
109        self.weights = weights;
110    }
111
112    /// Check if a configuration is a valid feedback vertex set.
113    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
114        if config.len() != self.graph.num_vertices() {
115            return false;
116        }
117        let keep: Vec<bool> = config.iter().map(|&c| c == 0).collect();
118        self.graph.induced_subgraph(&keep).is_dag()
119    }
120}
121
122impl<W: WeightElement> MinimumFeedbackVertexSet<W> {
123    /// Check if the problem has non-unit weights.
124    pub fn is_weighted(&self) -> bool {
125        !W::IS_UNIT
126    }
127
128    /// Get the number of vertices in the underlying directed graph.
129    pub fn num_vertices(&self) -> usize {
130        self.graph.num_vertices()
131    }
132
133    /// Get the number of arcs in the underlying directed graph.
134    pub fn num_arcs(&self) -> usize {
135        self.graph.num_arcs()
136    }
137}
138
139impl<W> Problem for MinimumFeedbackVertexSet<W>
140where
141    W: WeightElement + crate::variant::VariantParam,
142{
143    const NAME: &'static str = "MinimumFeedbackVertexSet";
144    type Solution = Vec<bool>;
145    type Value = Min<W::Sum>;
146
147    crate::problem_parameters![("num_arcs", num_arcs), ("num_vertices", num_vertices),];
148
149    fn variant() -> Vec<(&'static str, &'static str)> {
150        crate::variant_params![W]
151    }
152
153    fn evaluate(
154        &self,
155        config: &Self::Solution,
156    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
157        Ok({
158            if config.len() != self.graph.num_vertices() {
159                return Err(crate::traits::EvaluationError::InvalidConfiguration(
160                    "vertex-selection length does not match the graph".into(),
161                ));
162            }
163            // keep[v] = true if vertex v is NOT selected for removal
164            let keep: Vec<bool> = config.iter().map(|&removed| !removed).collect();
165            let subgraph = self.graph.induced_subgraph(&keep);
166            if !subgraph.is_dag() {
167                return Ok(Min(None));
168            }
169            let mut total = W::Sum::zero();
170            for (i, &selected) in config.iter().enumerate() {
171                if selected {
172                    total = W::checked_add_to_sum(
173                        total,
174                        self.weights[i].to_sum(),
175                        "summing selected feedback-vertex weights",
176                    )?;
177                }
178            }
179            Min(Some(total))
180        })
181    }
182}
183
184impl<W> crate::solvers::BruteForceProblem for MinimumFeedbackVertexSet<W>
185where
186    W: WeightElement + crate::variant::VariantParam,
187{
188    fn dimensions(&self) -> Vec<usize> {
189        vec![2; self.graph.num_vertices()]
190    }
191}
192
193#[derive(Debug, Deserialize, crate::CreateSpec)]
194struct MinimumFeedbackVertexSetOneCreateSpec {
195    /// The underlying graph.
196    graph: DirectedGraph,
197}
198
199impl TryFrom<MinimumFeedbackVertexSetOneCreateSpec> for MinimumFeedbackVertexSet<One> {
200    type Error = crate::registry::ConstructionError;
201    fn try_from(spec: MinimumFeedbackVertexSetOneCreateSpec) -> Result<Self, Self::Error> {
202        let weights = vec![One; spec.graph.num_vertices()];
203        Ok(Self::new(spec.graph, weights))
204    }
205}
206
207crate::declare_variants! {
208    default MinimumFeedbackVertexSet<i64> => "1.9977^num_vertices" create MinimumFeedbackVertexSetCreateSpec<i64>,
209    MinimumFeedbackVertexSet<One> => "1.9977^num_vertices" create MinimumFeedbackVertexSetOneCreateSpec,
210}
211
212crate::register_brute_force! {
213    MinimumFeedbackVertexSet<i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
214    MinimumFeedbackVertexSet<One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
215}
216
217#[cfg(feature = "example-db")]
218pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
219    use crate::topology::DirectedGraph;
220    vec![
221        crate::example_db::specs::ModelExampleSpec {
222            id: "minimum_feedback_vertex_set",
223            instance: Box::new(MinimumFeedbackVertexSet::new(
224                DirectedGraph::new(
225                    5,
226                    vec![(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 1), (4, 2)],
227                ),
228                vec![1i64; 5],
229            )),
230            optimal_config: serde_json::json!(vec![true, false, false, false, false]),
231            optimal_value: serde_json::json!(1),
232        },
233        crate::example_db::specs::ModelExampleSpec {
234            id: "minimum_feedback_vertex_set_unit",
235            instance: Box::new(MinimumFeedbackVertexSet::new(
236                DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]),
237                vec![One; 3],
238            )),
239            optimal_config: serde_json::json!(vec![true, false, false]),
240            optimal_value: serde_json::json!(1),
241        },
242    ]
243}
244
245/// Check if a set of vertices is a feedback vertex set (removing them makes the graph a DAG).
246///
247/// # Panics
248/// Panics if `selected.len() != graph.num_vertices()`.
249#[cfg(test)]
250pub(crate) fn is_feedback_vertex_set(graph: &DirectedGraph, selected: &[bool]) -> bool {
251    assert_eq!(
252        selected.len(),
253        graph.num_vertices(),
254        "selected length must match num_vertices"
255    );
256    // keep = NOT selected
257    let keep: Vec<bool> = selected.iter().map(|&s| !s).collect();
258    graph.induced_subgraph(&keep).is_dag()
259}
260
261#[cfg(test)]
262#[path = "../../unit_tests/models/graph/minimum_feedback_vertex_set.rs"]
263mod tests;
problemreductions/models/graph/minimum_feedback_vertex_set.rs

problemreductions/models/graph/
minimum_feedback_vertex_set.rs
