problemreductions/models/graph/
partial_feedback_edge_set.rs

1//! Partial Feedback Edge Set problem implementation.
2//!
3//! The Partial Feedback Edge Set problem asks whether removing at most `K`
4//! edges can hit every cycle of length at most `L`.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10#[cfg(feature = "example-db")]
11use std::collections::BTreeSet;
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "PartialFeedbackEdgeSet",
16        display_name: "Partial Feedback Edge Set",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Remove at most K edges so that every cycle of length at most L is hit",
24        fields: PartialFeedbackEdgeSetCreateSpec::FIELDS,
25    }
26}
27
28/// The Partial Feedback Edge Set problem.
29///
30/// Given an undirected graph `G = (V, E)`, a budget `K`, and a cycle-length
31/// bound `L`, determine whether there exists a subset `E' ⊆ E` such that:
32/// - `|E'| <= K`
33/// - every simple cycle in `G` with length at most `L` contains an edge in `E'`
34///
35/// Each edge has one binary decision variable:
36/// - `0`: keep the edge
37/// - `1`: remove the edge
38#[derive(Debug, Clone, Serialize, Deserialize)]
39#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
40pub struct PartialFeedbackEdgeSet<G> {
41    graph: G,
42    budget: usize,
43    max_cycle_length: usize,
44}
45
46#[derive(Debug, Deserialize, crate::CreateSpec)]
47struct PartialFeedbackEdgeSetCreateSpec {
48    /// The underlying graph G=(V,E).
49    graph: SimpleGraph,
50    /// Maximum number K of edges that may be removed.
51    budget: usize,
52    /// Cycle length bound L.
53    max_cycle_length: usize,
54}
55
56impl TryFrom<PartialFeedbackEdgeSetCreateSpec> for PartialFeedbackEdgeSet<SimpleGraph> {
57    type Error = crate::registry::ConstructionError;
58    fn try_from(spec: PartialFeedbackEdgeSetCreateSpec) -> Result<Self, Self::Error> {
59        Ok(Self::new(spec.graph, spec.budget, spec.max_cycle_length))
60    }
61}
62
63impl<G: Graph> PartialFeedbackEdgeSet<G> {
64    /// Create a new Partial Feedback Edge Set instance.
65    pub fn new(graph: G, budget: usize, max_cycle_length: usize) -> Self {
66        Self {
67            graph,
68            budget,
69            max_cycle_length,
70        }
71    }
72
73    /// Get a reference to the underlying graph.
74    pub fn graph(&self) -> &G {
75        &self.graph
76    }
77
78    /// Get the edge-removal budget `K`.
79    pub fn budget(&self) -> usize {
80        self.budget
81    }
82
83    /// Get the cycle-length bound `L`.
84    pub fn max_cycle_length(&self) -> usize {
85        self.max_cycle_length
86    }
87
88    /// Get the number of vertices in the graph.
89    pub fn num_vertices(&self) -> usize {
90        self.graph.num_vertices()
91    }
92
93    /// Get the number of edges in the graph.
94    pub fn num_edges(&self) -> usize {
95        self.graph.num_edges()
96    }
97
98    /// Check whether a configuration is a satisfying partial feedback edge set.
99    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
100        if config.len() != self.num_edges() {
101            return false;
102        }
103
104        let removed_edges = config.iter().filter(|&&removed| removed).count();
105        if removed_edges > self.budget {
106            return false;
107        }
108
109        let kept_edges: Vec<bool> = config.iter().map(|&removed| !removed).collect();
110        !has_cycle_with_length_at_most(&self.graph, &kept_edges, self.max_cycle_length)
111    }
112}
113
114impl<G> Problem for PartialFeedbackEdgeSet<G>
115where
116    G: Graph + crate::variant::VariantParam,
117{
118    const NAME: &'static str = "PartialFeedbackEdgeSet";
119    type Solution = Vec<bool>;
120    type Value = crate::types::Or;
121
122    crate::problem_parameters![
123        ("num_vertices", num_vertices),
124        ("num_edges", num_edges),
125        ("max_cycle_length", max_cycle_length),
126        ("budget", budget),
127    ];
128
129    fn variant() -> Vec<(&'static str, &'static str)> {
130        crate::variant_params![G]
131    }
132
133    fn evaluate(
134        &self,
135        config: &Self::Solution,
136    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
137        if config.len() != self.num_edges() {
138            return Err(crate::traits::EvaluationError::InvalidConfiguration(
139                "edge-selection length does not match the graph".into(),
140            ));
141        }
142        Ok(crate::types::Or(self.is_valid_solution(config)))
143    }
144}
145
146impl<G> crate::solvers::BruteForceProblem for PartialFeedbackEdgeSet<G>
147where
148    G: Graph + crate::variant::VariantParam,
149{
150    fn dimensions(&self) -> Vec<usize> {
151        vec![2; self.num_edges()]
152    }
153}
154
155fn has_cycle_with_length_at_most<G: Graph>(
156    graph: &G,
157    kept_edges: &[bool],
158    max_cycle_length: usize,
159) -> bool {
160    if kept_edges.len() != graph.num_edges() || max_cycle_length < 3 || graph.num_vertices() < 3 {
161        return false;
162    }
163
164    let mut adjacency = vec![Vec::new(); graph.num_vertices()];
165    for (keep, (u, v)) in kept_edges.iter().copied().zip(graph.edges()) {
166        if keep {
167            adjacency[u].push(v);
168            adjacency[v].push(u);
169        }
170    }
171
172    let mut visited = vec![false; graph.num_vertices()];
173    for start in 0..graph.num_vertices() {
174        visited[start] = true;
175        for &neighbor in &adjacency[start] {
176            if neighbor <= start {
177                continue;
178            }
179            visited[neighbor] = true;
180            if dfs_short_cycle(
181                &adjacency,
182                start,
183                neighbor,
184                1,
185                max_cycle_length,
186                &mut visited,
187            ) {
188                return true;
189            }
190            visited[neighbor] = false;
191        }
192        visited[start] = false;
193    }
194
195    false
196}
197
198fn dfs_short_cycle(
199    adjacency: &[Vec<usize>],
200    start: usize,
201    current: usize,
202    path_length: usize,
203    max_cycle_length: usize,
204    visited: &mut [bool],
205) -> bool {
206    for &neighbor in &adjacency[current] {
207        if neighbor == start {
208            let cycle_length = path_length + 1;
209            if cycle_length >= 3 && cycle_length <= max_cycle_length {
210                return true;
211            }
212            continue;
213        }
214
215        if visited[neighbor] || neighbor <= start || path_length + 1 >= max_cycle_length {
216            continue;
217        }
218
219        visited[neighbor] = true;
220        if dfs_short_cycle(
221            adjacency,
222            start,
223            neighbor,
224            path_length + 1,
225            max_cycle_length,
226            visited,
227        ) {
228            return true;
229        }
230        visited[neighbor] = false;
231    }
232
233    false
234}
235
236#[cfg(feature = "example-db")]
237pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
238    let graph = SimpleGraph::new(
239        6,
240        vec![
241            (0, 1),
242            (1, 2),
243            (2, 0),
244            (2, 3),
245            (3, 4),
246            (4, 2),
247            (3, 5),
248            (5, 4),
249            (0, 3),
250        ],
251    );
252    let chosen: BTreeSet<_> = [(0, 2), (2, 3), (3, 4)]
253        .into_iter()
254        .map(|(u, v)| normalize_edge(u, v))
255        .collect();
256    let optimal_config: Vec<bool> = graph
257        .edges()
258        .into_iter()
259        .map(|(u, v)| chosen.contains(&normalize_edge(u, v)))
260        .collect();
261
262    vec![crate::example_db::specs::ModelExampleSpec {
263        id: "partial_feedback_edge_set_simplegraph",
264        instance: Box::new(PartialFeedbackEdgeSet::new(graph, 3, 4)),
265        optimal_config: serde_json::to_value(optimal_config)
266            .expect("solution serialization must succeed"),
267        optimal_value: serde_json::json!(true),
268    }]
269}
270
271#[cfg(any(feature = "example-db", test))]
272fn normalize_edge(u: usize, v: usize) -> (usize, usize) {
273    if u <= v {
274        (u, v)
275    } else {
276        (v, u)
277    }
278}
279
280crate::declare_variants! {
281    default PartialFeedbackEdgeSet<SimpleGraph> => "2^num_edges" create PartialFeedbackEdgeSetCreateSpec,
282}
283
284crate::register_brute_force! {
285    PartialFeedbackEdgeSet<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
286}
287
288#[cfg(test)]
289#[path = "../../unit_tests/models/graph/partial_feedback_edge_set.rs"]
290mod tests;
problemreductions/models/graph/partial_feedback_edge_set.rs

problemreductions/models/graph/
partial_feedback_edge_set.rs
