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::{CreateSpec, ProblemSchemaEntry, 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", "i64"]),
27            VariantDimension::new("k", "KN", &["KN"]),
28        ],
29        category: crate::registry::ProblemCategory::Graph,
30        module_path: module_path!(),
31        description: "Find maximum-weight vertex subset whose induced subgraph has maximum degree at most k-1",
32        fields: MaximumCoKPlexCreateSpec::<One>::FIELDS,
33    }
34}
35
36/// The Maximum Co-k-Plex problem.
37///
38/// Given a graph `G = (V, E)`, vertex weights `w_v`, and an integer
39/// `k >= 1`, find `S ⊆ V` maximizing `Σ_{v ∈ S} w_v` subject to
40/// `deg_{G[S]}(v) <= k - 1` for every `v ∈ S` (equivalently, the induced
41/// subgraph has maximum degree at most `k - 1`).
42///
43/// # Type Parameters
44///
45/// * `G` - Graph type (e.g., [`SimpleGraph`]).
46/// * `W` - Weight type (e.g., [`One`], `i64`).
47/// * `K` - Compile-time [`KValue`] tag. [`KN`] stores `k` at runtime; fixed
48///   variants (`K1`, `K2`, ...) can be added later by registering more
49///   `declare_variants!` entries.
50///
51/// # Example
52///
53/// ```
54/// use problemreductions::models::graph::MaximumCoKPlex;
55/// use problemreductions::topology::SimpleGraph;
56/// use problemreductions::types::One;
57/// use problemreductions::variant::KN;
58/// use problemreductions::{BruteForce, Problem};
59///
60/// // 5-cycle C_5 with k = 2 (induced degree <= 1).
61/// let graph = SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]);
62/// let problem =
63///     MaximumCoKPlex::<_, One, KN>::with_k(graph, vec![One; 5], 2);
64/// assert_eq!(problem.bound_k(), 2);
65/// ```
66#[derive(Debug, Clone, Serialize, Deserialize)]
67#[serde(try_from = "MaximumCoKPlexData<G, W>")]
68#[serde(bound(
69    deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>, K: KValue"
70))]
71pub struct MaximumCoKPlex<G, W, K: KValue> {
72    /// The underlying graph.
73    graph: G,
74    /// Per-vertex weights `w_v`.
75    weights: Vec<W>,
76    /// Runtime co-k-plex parameter `k`. For compile-time `K` it equals `K::K`.
77    ///
78    /// Intentionally has no serde default: a malformed JSON missing
79    /// `bound_k` (e.g. for the `KN` variant) must fail loudly at load time
80    /// rather than silently fall back to `0`, which would make every
81    /// `evaluate()` infeasible.
82    bound_k: usize,
83    #[serde(skip)]
84    _phantom: std::marker::PhantomData<K>,
85}
86
87#[derive(Deserialize)]
88struct MaximumCoKPlexData<G, W> {
89    graph: G,
90    weights: Vec<W>,
91    bound_k: usize,
92}
93
94impl<G, W, K> TryFrom<MaximumCoKPlexData<G, W>> for MaximumCoKPlex<G, W, K>
95where
96    G: Graph,
97    W: Clone + Default,
98    K: KValue,
99{
100    type Error = crate::registry::ConstructionError;
101
102    fn try_from(data: MaximumCoKPlexData<G, W>) -> Result<Self, Self::Error> {
103        Self::try_with_k(data.graph, data.weights, data.bound_k)
104    }
105}
106
107#[derive(Debug, Deserialize, crate::CreateSpec)]
108struct MaximumCoKPlexCreateSpec<W> {
109    /// The underlying graph G=(V,E).
110    graph: SimpleGraph,
111    /// Vertex weights w: V -> R.
112    weights: Vec<W>,
113    /// Co-k-plex parameter k >= 1.
114    k: usize,
115}
116
117impl<W: Clone + Default> TryFrom<MaximumCoKPlexCreateSpec<W>>
118    for MaximumCoKPlex<SimpleGraph, W, KN>
119{
120    type Error = crate::registry::ConstructionError;
121
122    fn try_from(spec: MaximumCoKPlexCreateSpec<W>) -> Result<Self, Self::Error> {
123        Self::try_with_k(spec.graph, spec.weights, spec.k)
124    }
125}
126
127impl<G: Graph, W: Clone + Default, K: KValue> MaximumCoKPlex<G, W, K> {
128    /// Create an instance with an explicit runtime `k`.
129    ///
130    /// # Panics
131    /// Panics if `weights.len()` does not match `graph.num_vertices()`, if
132    /// `bound_k == 0`, or if `K` declares a fixed value that disagrees with
133    /// `bound_k`.
134    pub fn with_k(graph: G, weights: Vec<W>, bound_k: usize) -> Self {
135        Self::try_with_k(graph, weights, bound_k).unwrap_or_else(|error| panic!("{error}"))
136    }
137
138    fn try_with_k(
139        graph: G,
140        weights: Vec<W>,
141        bound_k: usize,
142    ) -> Result<Self, crate::registry::ConstructionError> {
143        if weights.len() != graph.num_vertices() {
144            return Err(crate::registry::ConstructionError::length_mismatch(
145                "weights",
146                weights.len(),
147                graph.num_vertices(),
148            ));
149        }
150        if bound_k == 0 {
151            return Err("co-k-plex parameter k must be at least 1".into());
152        }
153        if let Some(fixed) = K::K {
154            if fixed != bound_k {
155                return Err("fixed K type disagrees with runtime bound_k".into());
156            }
157        }
158        Ok(Self {
159            graph,
160            weights,
161            bound_k,
162            _phantom: std::marker::PhantomData,
163        })
164    }
165
166    /// Create a new instance using the compile-time `K`.
167    ///
168    /// # Panics
169    /// Panics if `K` is [`KN`] (use [`MaximumCoKPlex::with_k`] instead) or if
170    /// `weights.len()` does not match `graph.num_vertices()`.
171    pub fn new(graph: G, weights: Vec<W>) -> Self {
172        let k = K::K.expect("KN requires with_k");
173        Self::with_k(graph, weights, k)
174    }
175
176    /// Get a reference to the underlying graph.
177    pub fn graph(&self) -> &G {
178        &self.graph
179    }
180
181    /// Get a reference to the vertex weights.
182    pub fn weights(&self) -> &[W] {
183        &self.weights
184    }
185
186    /// Co-k-plex parameter `k`.
187    pub fn bound_k(&self) -> usize {
188        self.bound_k
189    }
190
191    /// Check if the problem uses a non-unit weight type.
192    pub fn is_weighted(&self) -> bool
193    where
194        W: WeightElement,
195    {
196        !W::IS_UNIT
197    }
198
199    /// Check if a configuration satisfies the co-k-plex constraint.
200    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
201        is_co_k_plex_config(&self.graph, config, self.bound_k)
202    }
203}
204
205impl<G: Graph, W: WeightElement, K: KValue> MaximumCoKPlex<G, W, K> {
206    /// Number of vertices in the underlying graph.
207    pub fn num_vertices(&self) -> usize {
208        self.graph.num_vertices()
209    }
210
211    /// Number of edges in the underlying graph.
212    pub fn num_edges(&self) -> usize {
213        self.graph.num_edges()
214    }
215}
216
217impl<G, W, K> Problem for MaximumCoKPlex<G, W, K>
218where
219    G: Graph + VariantParam,
220    W: WeightElement + VariantParam,
221    K: KValue,
222{
223    const NAME: &'static str = "MaximumCoKPlex";
224    type Solution = Vec<bool>;
225    type Value = Max<W::Sum>;
226
227    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
228
229    fn variant() -> Vec<(&'static str, &'static str)> {
230        crate::variant_params![G, W, K]
231    }
232
233    fn evaluate(
234        &self,
235        config: &Self::Solution,
236    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
237        if config.len() != self.graph.num_vertices() {
238            return Err(crate::traits::EvaluationError::InvalidConfiguration(
239                "vertex-selection length does not match the graph".into(),
240            ));
241        }
242        Ok({
243            if !is_co_k_plex_config(&self.graph, config, self.bound_k) {
244                return Ok(Max(None));
245            }
246            let mut total = W::Sum::zero();
247            for (i, &selected) in config.iter().enumerate() {
248                if selected {
249                    total = W::checked_add_to_sum(
250                        total,
251                        self.weights[i].to_sum(),
252                        "summing selected co-k-plex weights",
253                    )?;
254                }
255            }
256            Max(Some(total))
257        })
258    }
259}
260
261impl<G, W, K> crate::solvers::BruteForceProblem for MaximumCoKPlex<G, W, K>
262where
263    G: Graph + VariantParam,
264    W: WeightElement + VariantParam,
265    K: KValue,
266{
267    fn dimensions(&self) -> Vec<usize> {
268        vec![2; self.graph.num_vertices()]
269    }
270}
271
272/// Return true iff every selected vertex has at most `k - 1` selected
273/// neighbours in the induced subgraph.
274fn is_co_k_plex_config<G: Graph>(graph: &G, config: &[bool], bound_k: usize) -> bool {
275    if bound_k == 0 {
276        return false;
277    }
278    let n = graph.num_vertices();
279    let mut induced_degree = vec![0usize; n];
280    for (u, v) in graph.edges() {
281        let u_selected = config.get(u).copied().unwrap_or(false);
282        let v_selected = config.get(v).copied().unwrap_or(false);
283        if u_selected && v_selected {
284            induced_degree[u] += 1;
285            induced_degree[v] += 1;
286            if induced_degree[u] > bound_k - 1 || induced_degree[v] > bound_k - 1 {
287                return false;
288            }
289        }
290    }
291    true
292}
293
294#[derive(Debug, Deserialize, crate::CreateSpec)]
295struct MaximumCoKPlexOneCreateSpec {
296    /// The underlying graph.
297    graph: SimpleGraph,
298    k: usize,
299}
300
301impl TryFrom<MaximumCoKPlexOneCreateSpec> for MaximumCoKPlex<SimpleGraph, One, KN> {
302    type Error = crate::registry::ConstructionError;
303    fn try_from(spec: MaximumCoKPlexOneCreateSpec) -> Result<Self, Self::Error> {
304        let weights = vec![One; spec.graph.num_vertices()];
305        Self::try_with_k(spec.graph, weights, spec.k)
306    }
307}
308
309crate::declare_variants! {
310    default MaximumCoKPlex<SimpleGraph, One, KN> => "2^num_vertices" create MaximumCoKPlexOneCreateSpec,
311    MaximumCoKPlex<SimpleGraph, i64, KN>          => "2^num_vertices" create MaximumCoKPlexCreateSpec<i64>,
312}
313
314crate::register_brute_force! {
315    MaximumCoKPlex<SimpleGraph, One, KN> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
316    MaximumCoKPlex<SimpleGraph, i64, KN> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
317}
318
319#[cfg(feature = "example-db")]
320pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
321    vec![crate::example_db::specs::ModelExampleSpec {
322        id: "maximum_co_k_plex_simplegraph",
323        instance: Box::new(MaximumCoKPlex::<_, i64, KN>::with_k(
324            SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]),
325            vec![5, 1, 4, 1, 3],
326            2,
327        )),
328        optimal_config: serde_json::json!([true, false, true, false, true]),
329        optimal_value: serde_json::json!(12),
330    }]
331}
332
333#[cfg(test)]
334#[path = "../../unit_tests/models/graph/maximum_co_k_plex.rs"]
335mod tests;
problemreductions/models/graph/maximum_co_k_plex.rs

problemreductions/models/graph/
maximum_co_k_plex.rs
