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::{FieldInfo, 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        module_path: module_path!(),
22        description: "Remove at most K edges so that every cycle of length at most L is hit",
23        fields: &[
24            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
25            FieldInfo { name: "budget", type_name: "usize", description: "Maximum number K of edges that may be removed" },
26            FieldInfo { name: "max_cycle_length", type_name: "usize", description: "Cycle length bound L; every cycle with length at most L must be hit" },
27        ],
28    }
29}
30
31/// The Partial Feedback Edge Set problem.
32///
33/// Given an undirected graph `G = (V, E)`, a budget `K`, and a cycle-length
34/// bound `L`, determine whether there exists a subset `E' ⊆ E` such that:
35/// - `|E'| <= K`
36/// - every simple cycle in `G` with length at most `L` contains an edge in `E'`
37///
38/// Each edge has one binary decision variable:
39/// - `0`: keep the edge
40/// - `1`: remove the edge
41#[derive(Debug, Clone, Serialize, Deserialize)]
42#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
43pub struct PartialFeedbackEdgeSet<G> {
44    graph: G,
45    budget: usize,
46    max_cycle_length: usize,
47}
48
49impl<G: Graph> PartialFeedbackEdgeSet<G> {
50    /// Create a new Partial Feedback Edge Set instance.
51    pub fn new(graph: G, budget: usize, max_cycle_length: usize) -> Self {
52        Self {
53            graph,
54            budget,
55            max_cycle_length,
56        }
57    }
58
59    /// Get a reference to the underlying graph.
60    pub fn graph(&self) -> &G {
61        &self.graph
62    }
63
64    /// Get the edge-removal budget `K`.
65    pub fn budget(&self) -> usize {
66        self.budget
67    }
68
69    /// Get the cycle-length bound `L`.
70    pub fn max_cycle_length(&self) -> usize {
71        self.max_cycle_length
72    }
73
74    /// Get the number of vertices in the graph.
75    pub fn num_vertices(&self) -> usize {
76        self.graph.num_vertices()
77    }
78
79    /// Get the number of edges in the graph.
80    pub fn num_edges(&self) -> usize {
81        self.graph.num_edges()
82    }
83
84    /// Check whether a configuration is a satisfying partial feedback edge set.
85    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
86        if config.len() != self.num_edges() || config.iter().any(|&value| value > 1) {
87            return false;
88        }
89
90        let removed_edges = config.iter().filter(|&&value| value == 1).count();
91        if removed_edges > self.budget {
92            return false;
93        }
94
95        let kept_edges: Vec<bool> = config.iter().map(|&value| value == 0).collect();
96        !has_cycle_with_length_at_most(&self.graph, &kept_edges, self.max_cycle_length)
97    }
98}
99
100impl<G> Problem for PartialFeedbackEdgeSet<G>
101where
102    G: Graph + crate::variant::VariantParam,
103{
104    const NAME: &'static str = "PartialFeedbackEdgeSet";
105    type Value = crate::types::Or;
106
107    fn variant() -> Vec<(&'static str, &'static str)> {
108        crate::variant_params![G]
109    }
110
111    fn dims(&self) -> Vec<usize> {
112        vec![2; self.num_edges()]
113    }
114
115    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
116        crate::types::Or(self.is_valid_solution(config))
117    }
118}
119
120fn has_cycle_with_length_at_most<G: Graph>(
121    graph: &G,
122    kept_edges: &[bool],
123    max_cycle_length: usize,
124) -> bool {
125    if kept_edges.len() != graph.num_edges() || max_cycle_length < 3 || graph.num_vertices() < 3 {
126        return false;
127    }
128
129    let mut adjacency = vec![Vec::new(); graph.num_vertices()];
130    for (keep, (u, v)) in kept_edges.iter().copied().zip(graph.edges()) {
131        if keep {
132            adjacency[u].push(v);
133            adjacency[v].push(u);
134        }
135    }
136
137    let mut visited = vec![false; graph.num_vertices()];
138    for start in 0..graph.num_vertices() {
139        visited[start] = true;
140        for &neighbor in &adjacency[start] {
141            if neighbor <= start {
142                continue;
143            }
144            visited[neighbor] = true;
145            if dfs_short_cycle(
146                &adjacency,
147                start,
148                neighbor,
149                1,
150                max_cycle_length,
151                &mut visited,
152            ) {
153                return true;
154            }
155            visited[neighbor] = false;
156        }
157        visited[start] = false;
158    }
159
160    false
161}
162
163fn dfs_short_cycle(
164    adjacency: &[Vec<usize>],
165    start: usize,
166    current: usize,
167    path_length: usize,
168    max_cycle_length: usize,
169    visited: &mut [bool],
170) -> bool {
171    for &neighbor in &adjacency[current] {
172        if neighbor == start {
173            let cycle_length = path_length + 1;
174            if cycle_length >= 3 && cycle_length <= max_cycle_length {
175                return true;
176            }
177            continue;
178        }
179
180        if visited[neighbor] || neighbor <= start || path_length + 1 >= max_cycle_length {
181            continue;
182        }
183
184        visited[neighbor] = true;
185        if dfs_short_cycle(
186            adjacency,
187            start,
188            neighbor,
189            path_length + 1,
190            max_cycle_length,
191            visited,
192        ) {
193            return true;
194        }
195        visited[neighbor] = false;
196    }
197
198    false
199}
200
201#[cfg(feature = "example-db")]
202pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
203    let graph = SimpleGraph::new(
204        6,
205        vec![
206            (0, 1),
207            (1, 2),
208            (2, 0),
209            (2, 3),
210            (3, 4),
211            (4, 2),
212            (3, 5),
213            (5, 4),
214            (0, 3),
215        ],
216    );
217    let chosen: BTreeSet<_> = [(0, 2), (2, 3), (3, 4)]
218        .into_iter()
219        .map(|(u, v)| normalize_edge(u, v))
220        .collect();
221    let optimal_config = graph
222        .edges()
223        .into_iter()
224        .map(|(u, v)| usize::from(chosen.contains(&normalize_edge(u, v))))
225        .collect();
226
227    vec![crate::example_db::specs::ModelExampleSpec {
228        id: "partial_feedback_edge_set_simplegraph",
229        instance: Box::new(PartialFeedbackEdgeSet::new(graph, 3, 4)),
230        optimal_config,
231        optimal_value: serde_json::json!(true),
232    }]
233}
234
235#[cfg(any(feature = "example-db", test))]
236fn normalize_edge(u: usize, v: usize) -> (usize, usize) {
237    if u <= v {
238        (u, v)
239    } else {
240        (v, u)
241    }
242}
243
244crate::declare_variants! {
245    default PartialFeedbackEdgeSet<SimpleGraph> => "2^num_edges",
246}
247
248#[cfg(test)]
249#[path = "../../unit_tests/models/graph/partial_feedback_edge_set.rs"]
250mod tests;
problemreductions/models/graph/partial_feedback_edge_set.rs

problemreductions/models/graph/
partial_feedback_edge_set.rs
