problemreductions/models/graph/
kclique.rs

1//! KClique problem implementation.
2//!
3//! KClique is the decision version of Clique: determine whether a graph
4//! contains a clique of size at least `k`.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "KClique",
14        display_name: "k-Clique",
15        aliases: &["Clique"],
16        dimensions: &[VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"])],
17        category: crate::registry::ProblemCategory::Graph,
18        module_path: module_path!(),
19        description: "Determine whether a graph contains a clique of size at least k",
20        fields: KCliqueCreateSpec::FIELDS,
21    }
22}
23
24/// The k-Clique decision problem.
25///
26/// Given a graph `G = (V, E)` and a positive integer `k`, determine whether
27/// there exists a subset `K ⊆ V` of size at least `k` such that every pair of
28/// distinct vertices in `K` is adjacent.
29#[derive(Debug, Clone, Serialize, Deserialize)]
30pub struct KClique<G> {
31    graph: G,
32    k: usize,
33}
34
35#[derive(Debug, Deserialize, crate::CreateSpec)]
36struct KCliqueCreateSpec {
37    #[create(codec = "edge-list")]
38    graph: Vec<(usize, usize)>,
39    num_vertices: Option<usize>,
40    k: usize,
41}
42
43impl TryFrom<KCliqueCreateSpec> for KClique<SimpleGraph> {
44    type Error = crate::registry::ConstructionError;
45    fn try_from(spec: KCliqueCreateSpec) -> Result<Self, Self::Error> {
46        if spec.graph.is_empty() && spec.num_vertices.is_none() {
47            return Err("num_vertices is required for an empty graph".into());
48        }
49        for &(u, v) in &spec.graph {
50            if u == v {
51                return Err(format!("self-loop {u}-{v} is not allowed").into());
52            }
53        }
54        let inferred = spec
55            .graph
56            .iter()
57            .flat_map(|&(u, v)| [u, v])
58            .max()
59            .map(|v| v.checked_add(1).ok_or("vertex count overflows usize"))
60            .transpose()?
61            .unwrap_or(0);
62        let count = spec.num_vertices.unwrap_or(inferred);
63        if count < inferred {
64            return Err("num_vertices is too small for graph endpoints".into());
65        }
66        if spec.k == 0 {
67            return Err("k must be positive".into());
68        }
69        if spec.k > count {
70            return Err("k must be <= graph num_vertices".into());
71        }
72        Ok(Self {
73            graph: SimpleGraph::new(count, spec.graph),
74            k: spec.k,
75        })
76    }
77}
78
79impl<G: Graph> KClique<G> {
80    /// Create a new k-Clique problem instance.
81    pub fn new(graph: G, k: usize) -> Self {
82        assert!(k > 0, "k must be positive");
83        assert!(k <= graph.num_vertices(), "k must be <= graph num_vertices");
84        Self { graph, k }
85    }
86
87    /// Get a reference to the underlying graph.
88    pub fn graph(&self) -> &G {
89        &self.graph
90    }
91
92    /// Get the clique-size threshold.
93    pub fn k(&self) -> usize {
94        self.k
95    }
96
97    /// Get the number of vertices in the underlying graph.
98    pub fn num_vertices(&self) -> usize {
99        self.graph.num_vertices()
100    }
101
102    /// Get the number of edges in the underlying graph.
103    pub fn num_edges(&self) -> usize {
104        self.graph.num_edges()
105    }
106
107    /// Check whether a configuration is a valid witness.
108    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
109        is_kclique_config(&self.graph, config, self.k)
110    }
111
112    /// Build a binary selection config from the listed vertices.
113    pub fn config_from_vertices(num_vertices: usize, selected_vertices: &[usize]) -> Vec<bool> {
114        let mut config = vec![false; num_vertices];
115        for &vertex in selected_vertices {
116            config[vertex] = true;
117        }
118        config
119    }
120
121    /// Convenience wrapper around [`Self::config_from_vertices`] using `self.num_vertices()`.
122    pub fn config_from_selected_vertices(&self, selected_vertices: &[usize]) -> Vec<bool> {
123        Self::config_from_vertices(self.num_vertices(), selected_vertices)
124    }
125}
126
127impl<G> Problem for KClique<G>
128where
129    G: Graph + crate::variant::VariantParam,
130{
131    const NAME: &'static str = "KClique";
132    type Solution = Vec<bool>;
133    type Value = crate::types::Or;
134
135    crate::problem_parameters![
136        ("k", k),
137        ("num_edges", num_edges),
138        ("num_vertices", num_vertices),
139    ];
140
141    fn variant() -> Vec<(&'static str, &'static str)> {
142        crate::variant_params![G]
143    }
144
145    fn evaluate(
146        &self,
147        config: &Self::Solution,
148    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
149        if config.len() != self.graph.num_vertices() {
150            return Err(crate::traits::EvaluationError::InvalidConfiguration(
151                "vertex-selection length does not match the graph".into(),
152            ));
153        }
154        Ok(crate::types::Or(is_kclique_config(
155            &self.graph,
156            config,
157            self.k,
158        )))
159    }
160}
161
162impl<G> crate::solvers::BruteForceProblem for KClique<G>
163where
164    G: Graph + crate::variant::VariantParam,
165{
166    fn dimensions(&self) -> Vec<usize> {
167        vec![2; self.graph.num_vertices()]
168    }
169}
170
171fn is_kclique_config<G: Graph>(graph: &G, config: &[bool], k: usize) -> bool {
172    if config.len() != graph.num_vertices() {
173        return false;
174    }
175
176    let selected: Vec<usize> = config
177        .iter()
178        .enumerate()
179        .filter_map(|(index, &selected)| selected.then_some(index))
180        .collect();
181
182    if selected.len() < k {
183        return false;
184    }
185
186    for i in 0..selected.len() {
187        for j in (i + 1)..selected.len() {
188            if !graph.has_edge(selected[i], selected[j]) {
189                return false;
190            }
191        }
192    }
193    true
194}
195
196crate::impl_random_generate!(
197    KClique<SimpleGraph>,
198    crate::random::CliqueRandomSpec,
199    |spec| {
200        if spec.k == 0 || spec.k > spec.num_vertices {
201            return Err(format!(
202                "k must be between 1 and num_vertices ({})",
203                spec.num_vertices
204            )
205            .into());
206        }
207        Ok(KClique::new(spec.graph()?, spec.k))
208    }
209);
210
211crate::declare_variants! {
212    default KClique<SimpleGraph> => "1.1996^num_vertices" create KCliqueCreateSpec random,
213}
214
215crate::register_brute_force! {
216    KClique<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
217}
218
219#[cfg(feature = "example-db")]
220pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
221    vec![crate::example_db::specs::ModelExampleSpec {
222        id: "kclique_simplegraph",
223        instance: Box::new(KClique::new(
224            SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
225            3,
226        )),
227        optimal_config: serde_json::json!(vec![false, false, true, true, true]),
228        optimal_value: serde_json::json!(true),
229    }]
230}
231
232#[cfg(test)]
233#[path = "../../unit_tests/models/graph/kclique.rs"]
234mod tests;
problemreductions/models/graph/kclique.rs

problemreductions/models/graph/
kclique.rs
