problemreductions/models/graph/
maximum_co_k_plex.rs

1//! Maximum Co-k-Plex problem implementation.
2//!
3//! Given an undirected graph G = (V, E), vertex weights w: V -> R, and an
4//! integer k >= 1, find a subset S ⊆ V maximizing Σ_{v ∈ S} w(v) such that
5//! the induced subgraph G[S] has maximum degree at most k - 1. Equivalently,
6//! every selected vertex has at most k - 1 selected neighbours.
7//!
8//! For k = 1 the problem degenerates to [`MaximumIndependentSet`]; for larger
9//! k it is the maximum (k-1)-dependent set / co-k-plex.
10
11use crate::registry::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry, VariantDimension};
12use crate::topology::{Graph, SimpleGraph};
13use crate::traits::Problem;
14use crate::types::{Max, One, WeightElement};
15use crate::variant::{KValue, VariantParam, KN};
16use num_traits::Zero;
17use serde::{Deserialize, Serialize};
18
19inventory::submit! {
20    ProblemSchemaEntry {
21        name: "MaximumCoKPlex",
22        display_name: "Maximum Co-k-Plex",
23        aliases: &[],
24        dimensions: &[
25            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
26            VariantDimension::new("weight", "One", &["One", "i32"]),
27            VariantDimension::new("k", "KN", &["KN"]),
28        ],
29        module_path: module_path!(),
30        description: "Find maximum-weight vertex subset whose induced subgraph has maximum degree at most k-1",
31        fields: &[
32            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
33            FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
34            FieldInfo { name: "bound_k", type_name: "usize", description: "Co-k-plex parameter k >= 1; selected-vertex induced degree must be at most k-1" },
35        ],
36    }
37}
38
39inventory::submit! {
40    ProblemSizeFieldEntry {
41        name: "MaximumCoKPlex",
42        fields: &["num_vertices", "num_edges"],
43    }
44}
45
46/// The Maximum Co-k-Plex problem.
47///
48/// Given a graph `G = (V, E)`, vertex weights `w_v`, and an integer
49/// `k >= 1`, find `S ⊆ V` maximizing `Σ_{v ∈ S} w_v` subject to
50/// `deg_{G[S]}(v) <= k - 1` for every `v ∈ S` (equivalently, the induced
51/// subgraph has maximum degree at most `k - 1`).
52///
53/// # Type Parameters
54///
55/// * `G` - Graph type (e.g., [`SimpleGraph`]).
56/// * `W` - Weight type (e.g., [`One`], `i32`).
57/// * `K` - Compile-time [`KValue`] tag. [`KN`] stores `k` at runtime; fixed
58///   variants (`K1`, `K2`, ...) can be added later by registering more
59///   `declare_variants!` entries.
60///
61/// # Example
62///
63/// ```
64/// use problemreductions::models::graph::MaximumCoKPlex;
65/// use problemreductions::topology::SimpleGraph;
66/// use problemreductions::types::One;
67/// use problemreductions::variant::KN;
68/// use problemreductions::{BruteForce, Problem, Solver};
69///
70/// // 5-cycle C_5 with k = 2 (induced degree <= 1).
71/// let graph = SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]);
72/// let problem =
73///     MaximumCoKPlex::<_, One, KN>::with_k(graph, vec![One; 5], 2);
74/// assert_eq!(problem.bound_k(), 2);
75/// ```
76#[derive(Debug, Clone, Serialize, Deserialize)]
77#[serde(bound(deserialize = "G: serde::Deserialize<'de>, W: serde::Deserialize<'de>"))]
78pub struct MaximumCoKPlex<G, W, K: KValue> {
79    /// The underlying graph.
80    graph: G,
81    /// Per-vertex weights `w_v`.
82    weights: Vec<W>,
83    /// Runtime co-k-plex parameter `k`. For compile-time `K` it equals `K::K`.
84    ///
85    /// Intentionally has no serde default: a malformed JSON missing
86    /// `bound_k` (e.g. for the `KN` variant) must fail loudly at load time
87    /// rather than silently fall back to `0`, which would make every
88    /// `evaluate()` infeasible.
89    bound_k: usize,
90    #[serde(skip)]
91    _phantom: std::marker::PhantomData<K>,
92}
93
94impl<G: Graph, W: Clone + Default, K: KValue> MaximumCoKPlex<G, W, K> {
95    /// Create an instance with an explicit runtime `k`.
96    ///
97    /// # Panics
98    /// Panics if `weights.len()` does not match `graph.num_vertices()`, if
99    /// `bound_k == 0`, or if `K` declares a fixed value that disagrees with
100    /// `bound_k`.
101    pub fn with_k(graph: G, weights: Vec<W>, bound_k: usize) -> Self {
102        assert_eq!(
103            weights.len(),
104            graph.num_vertices(),
105            "weights length must match graph num_vertices"
106        );
107        assert!(bound_k >= 1, "co-k-plex parameter k must be at least 1");
108        if let Some(fixed) = K::K {
109            assert_eq!(
110                fixed, bound_k,
111                "fixed K type disagrees with runtime bound_k"
112            );
113        }
114        Self {
115            graph,
116            weights,
117            bound_k,
118            _phantom: std::marker::PhantomData,
119        }
120    }
121
122    /// Create a new instance using the compile-time `K`.
123    ///
124    /// # Panics
125    /// Panics if `K` is [`KN`] (use [`MaximumCoKPlex::with_k`] instead) or if
126    /// `weights.len()` does not match `graph.num_vertices()`.
127    pub fn new(graph: G, weights: Vec<W>) -> Self {
128        let k = K::K.expect("KN requires with_k");
129        Self::with_k(graph, weights, k)
130    }
131
132    /// Get a reference to the underlying graph.
133    pub fn graph(&self) -> &G {
134        &self.graph
135    }
136
137    /// Get a reference to the vertex weights.
138    pub fn weights(&self) -> &[W] {
139        &self.weights
140    }
141
142    /// Co-k-plex parameter `k`.
143    pub fn bound_k(&self) -> usize {
144        self.bound_k
145    }
146
147    /// Check if the problem uses a non-unit weight type.
148    pub fn is_weighted(&self) -> bool
149    where
150        W: WeightElement,
151    {
152        !W::IS_UNIT
153    }
154
155    /// Check if a configuration satisfies the co-k-plex constraint.
156    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
157        is_co_k_plex_config(&self.graph, config, self.bound_k)
158    }
159}
160
161impl<G: Graph, W: WeightElement, K: KValue> MaximumCoKPlex<G, W, K> {
162    /// Number of vertices in the underlying graph.
163    pub fn num_vertices(&self) -> usize {
164        self.graph.num_vertices()
165    }
166
167    /// Number of edges in the underlying graph.
168    pub fn num_edges(&self) -> usize {
169        self.graph.num_edges()
170    }
171}
172
173impl<G, W, K> Problem for MaximumCoKPlex<G, W, K>
174where
175    G: Graph + VariantParam,
176    W: WeightElement + VariantParam,
177    K: KValue,
178{
179    const NAME: &'static str = "MaximumCoKPlex";
180    type Value = Max<W::Sum>;
181
182    fn variant() -> Vec<(&'static str, &'static str)> {
183        crate::variant_params![G, W, K]
184    }
185
186    fn dims(&self) -> Vec<usize> {
187        vec![2; self.graph.num_vertices()]
188    }
189
190    fn evaluate(&self, config: &[usize]) -> Max<W::Sum> {
191        if !is_co_k_plex_config(&self.graph, config, self.bound_k) {
192            return Max(None);
193        }
194        let mut total = W::Sum::zero();
195        for (i, &selected) in config.iter().enumerate() {
196            if selected == 1 {
197                total += self.weights[i].to_sum();
198            }
199        }
200        Max(Some(total))
201    }
202}
203
204/// Return true iff every selected vertex has at most `k - 1` selected
205/// neighbours in the induced subgraph.
206fn is_co_k_plex_config<G: Graph>(graph: &G, config: &[usize], bound_k: usize) -> bool {
207    if bound_k == 0 {
208        return false;
209    }
210    let n = graph.num_vertices();
211    let mut induced_degree = vec![0usize; n];
212    for (u, v) in graph.edges() {
213        let u_selected = config.get(u).copied().unwrap_or(0) == 1;
214        let v_selected = config.get(v).copied().unwrap_or(0) == 1;
215        if u_selected && v_selected {
216            induced_degree[u] += 1;
217            induced_degree[v] += 1;
218            if induced_degree[u] > bound_k - 1 || induced_degree[v] > bound_k - 1 {
219                return false;
220            }
221        }
222    }
223    true
224}
225
226crate::declare_variants! {
227    default MaximumCoKPlex<SimpleGraph, One, KN> => "2^num_vertices",
228    MaximumCoKPlex<SimpleGraph, i32, KN>          => "2^num_vertices",
229}
230
231#[cfg(feature = "example-db")]
232pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
233    vec![crate::example_db::specs::ModelExampleSpec {
234        id: "maximum_co_k_plex_simplegraph_i32",
235        instance: Box::new(MaximumCoKPlex::<_, i32, KN>::with_k(
236            SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]),
237            vec![5, 1, 4, 1, 3],
238            2,
239        )),
240        optimal_config: vec![1, 0, 1, 0, 1],
241        optimal_value: serde_json::json!(12),
242    }]
243}
244
245#[cfg(test)]
246#[path = "../../unit_tests/models/graph/maximum_co_k_plex.rs"]
247mod tests;
problemreductions/models/graph/maximum_co_k_plex.rs

problemreductions/models/graph/
maximum_co_k_plex.rs
