problemreductions/models/graph/
minimum_vertex_cover.rs

1//! Vertex Covering problem implementation.
2//!
3//! The Vertex Cover problem asks for a minimum weight subset of vertices
4//! such that every edge has at least one endpoint in the subset.
5
6use crate::models::decision::Decision;
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::types::{Min, One, WeightElement};
11use num_traits::Zero;
12use serde::{Deserialize, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "MinimumVertexCover",
17        display_name: "Minimum Vertex Cover",
18        aliases: &["MVC"],
19        dimensions: &[
20            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
21            VariantDimension::new("weight", "i32", &["i32", "One"]),
22        ],
23        module_path: module_path!(),
24        description: "Find minimum weight vertex cover in a graph",
25        fields: &[
26            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
27            FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
28        ],
29    }
30}
31
32/// The Vertex Covering problem.
33///
34/// Given a graph G = (V, E) and weights w_v for each vertex,
35/// find a subset S ⊆ V such that:
36/// - Every edge has at least one endpoint in S (covering constraint)
37/// - The total weight Σ_{v ∈ S} w_v is minimized
38///
39/// # Example
40///
41/// ```
42/// use problemreductions::models::graph::MinimumVertexCover;
43/// use problemreductions::topology::SimpleGraph;
44/// use problemreductions::{Problem, Solver, BruteForce};
45///
46/// // Create a path graph 0-1-2
47/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
48/// let problem = MinimumVertexCover::new(graph, vec![1; 3]);
49///
50/// // Solve with brute force
51/// let solver = BruteForce::new();
52/// let solutions = solver.find_all_witnesses(&problem);
53///
54/// // Minimum vertex cover is just vertex 1
55/// assert!(solutions.contains(&vec![0, 1, 0]));
56/// ```
57#[derive(Debug, Clone, Serialize, Deserialize)]
58pub struct MinimumVertexCover<G, W> {
59    /// The underlying graph.
60    graph: G,
61    /// Weights for each vertex.
62    weights: Vec<W>,
63}
64
65impl<G: Graph, W: Clone + Default> MinimumVertexCover<G, W> {
66    /// Create a Vertex Covering problem from a graph with given weights.
67    pub fn new(graph: G, weights: Vec<W>) -> Self {
68        assert_eq!(
69            weights.len(),
70            graph.num_vertices(),
71            "weights length must match graph num_vertices"
72        );
73        Self { graph, weights }
74    }
75
76    /// Get a reference to the underlying graph.
77    pub fn graph(&self) -> &G {
78        &self.graph
79    }
80
81    /// Get a reference to the weights.
82    pub fn weights(&self) -> &[W] {
83        &self.weights
84    }
85
86    /// Check if the problem uses a non-unit weight type.
87    pub fn is_weighted(&self) -> bool
88    where
89        W: WeightElement,
90    {
91        !W::IS_UNIT
92    }
93
94    /// Check if a configuration is a valid vertex cover.
95    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
96        is_vertex_cover_config(&self.graph, config)
97    }
98}
99
100impl<G: Graph, W: WeightElement> MinimumVertexCover<G, W> {
101    /// Get the number of vertices in the underlying graph.
102    pub fn num_vertices(&self) -> usize {
103        self.graph().num_vertices()
104    }
105
106    /// Get the number of edges in the underlying graph.
107    pub fn num_edges(&self) -> usize {
108        self.graph().num_edges()
109    }
110}
111
112impl<G, W> Problem for MinimumVertexCover<G, W>
113where
114    G: Graph + crate::variant::VariantParam,
115    W: WeightElement + crate::variant::VariantParam,
116{
117    const NAME: &'static str = "MinimumVertexCover";
118    type Value = Min<W::Sum>;
119
120    fn variant() -> Vec<(&'static str, &'static str)> {
121        crate::variant_params![G, W]
122    }
123
124    fn dims(&self) -> Vec<usize> {
125        vec![2; self.graph.num_vertices()]
126    }
127
128    fn evaluate(&self, config: &[usize]) -> Min<W::Sum> {
129        if !is_vertex_cover_config(&self.graph, config) {
130            return Min(None);
131        }
132        let mut total = W::Sum::zero();
133        for (i, &selected) in config.iter().enumerate() {
134            if selected == 1 {
135                total += self.weights[i].to_sum();
136            }
137        }
138        Min(Some(total))
139    }
140}
141
142/// Check if a configuration forms a valid vertex cover.
143pub(crate) fn is_vertex_cover_config<G: Graph>(graph: &G, config: &[usize]) -> bool {
144    for (u, v) in graph.edges() {
145        let u_covered = config.get(u).copied().unwrap_or(0) == 1;
146        let v_covered = config.get(v).copied().unwrap_or(0) == 1;
147        if !u_covered && !v_covered {
148            return false;
149        }
150    }
151    true
152}
153
154crate::declare_variants! {
155    default MinimumVertexCover<SimpleGraph, i32> => "1.1996^num_vertices",
156    MinimumVertexCover<SimpleGraph, One> => "1.1996^num_vertices",
157}
158
159impl<G, W> crate::models::decision::DecisionProblemMeta for MinimumVertexCover<G, W>
160where
161    G: Graph + crate::variant::VariantParam,
162    W: WeightElement + crate::variant::VariantParam,
163    W::Sum: std::fmt::Debug + serde::Serialize + serde::de::DeserializeOwned,
164{
165    const DECISION_NAME: &'static str = "DecisionMinimumVertexCover";
166}
167
168impl Decision<MinimumVertexCover<SimpleGraph, i32>> {
169    /// Number of vertices in the underlying graph.
170    pub fn num_vertices(&self) -> usize {
171        self.inner().num_vertices()
172    }
173
174    /// Number of edges in the underlying graph.
175    pub fn num_edges(&self) -> usize {
176        self.inner().num_edges()
177    }
178
179    /// Decision bound as a nonnegative integer.
180    pub fn k(&self) -> usize {
181        (*self.bound()).try_into().unwrap_or(0)
182    }
183}
184
185crate::register_decision_variant!(
186    MinimumVertexCover<SimpleGraph, i32>,
187    "DecisionMinimumVertexCover",
188    "1.1996^num_vertices",
189    &["DMVC", "VC", "VertexCover"],
190    "Decision version: does a vertex cover of cost <= bound exist?",
191    dims: [
192        VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
193        VariantDimension::new("weight", "i32", &["i32"]),
194    ],
195    fields: [
196        FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
197        FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
198        FieldInfo { name: "bound", type_name: "i32", description: "Decision bound (maximum allowed cover cost)" },
199    ],
200    size_getters: [("num_vertices", num_vertices), ("num_edges", num_edges)]
201);
202
203#[cfg(feature = "example-db")]
204pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
205    vec![crate::example_db::specs::ModelExampleSpec {
206        id: "minimum_vertex_cover_simplegraph_i32",
207        instance: Box::new(MinimumVertexCover::new(
208            SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
209            vec![1i32; 5],
210        )),
211        optimal_config: vec![1, 0, 0, 1, 1],
212        optimal_value: serde_json::json!(3),
213    }]
214}
215
216#[cfg(feature = "example-db")]
217pub(crate) fn decision_canonical_model_example_specs(
218) -> Vec<crate::example_db::specs::ModelExampleSpec> {
219    vec![crate::example_db::specs::ModelExampleSpec {
220        id: "decision_minimum_vertex_cover_simplegraph_i32",
221        instance: Box::new(crate::models::decision::Decision::new(
222            MinimumVertexCover::new(
223                SimpleGraph::new(4, vec![(0, 1), (1, 2), (0, 2), (2, 3)]),
224                vec![1i32; 4],
225            ),
226            2,
227        )),
228        optimal_config: vec![1, 0, 1, 0],
229        optimal_value: serde_json::json!(true),
230    }]
231}
232
233#[cfg(feature = "example-db")]
234pub(crate) fn decision_canonical_rule_example_specs(
235) -> Vec<crate::example_db::specs::RuleExampleSpec> {
236    vec![crate::example_db::specs::RuleExampleSpec {
237        id: "decision_minimum_vertex_cover_to_minimum_vertex_cover",
238        build: || {
239            use crate::example_db::specs::assemble_rule_example;
240            use crate::export::SolutionPair;
241            use crate::rules::{AggregateReductionResult, ReduceToAggregate};
242
243            let source = crate::models::decision::Decision::new(
244                MinimumVertexCover::new(
245                    SimpleGraph::new(4, vec![(0, 1), (1, 2), (0, 2), (2, 3)]),
246                    vec![1i32; 4],
247                ),
248                2,
249            );
250            let result = source.reduce_to_aggregate();
251            let target = result.target_problem();
252            let config = vec![1, 0, 1, 0];
253            assemble_rule_example(
254                &source,
255                target,
256                vec![SolutionPair {
257                    source_config: config.clone(),
258                    target_config: config,
259                }],
260            )
261        },
262    }]
263}
264
265/// Check if a set of vertices forms a vertex cover.
266///
267/// # Arguments
268/// * `graph` - The graph
269/// * `selected` - Boolean slice indicating which vertices are selected
270///
271/// # Panics
272/// Panics if `selected.len() != graph.num_vertices()`.
273#[cfg(test)]
274pub(crate) fn is_vertex_cover<G: Graph>(graph: &G, selected: &[bool]) -> bool {
275    assert_eq!(
276        selected.len(),
277        graph.num_vertices(),
278        "selected length must match num_vertices"
279    );
280    for (u, v) in graph.edges() {
281        if !selected[u] && !selected[v] {
282            return false;
283        }
284    }
285    true
286}
287
288#[cfg(test)]
289#[path = "../../unit_tests/models/graph/minimum_vertex_cover.rs"]
290mod tests;
problemreductions/models/graph/minimum_vertex_cover.rs

problemreductions/models/graph/
minimum_vertex_cover.rs
