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

problemreductions/models/graph/
maximum_co_k_plex.rs
