problemreductions/rules/
kclique_conjunctivebooleanquery.rs

1//! Reduction from KClique to ConjunctiveBooleanQuery.
2//!
3//! Given a KClique instance (G=(V,E), k):
4//! 1. Domain D = V (n elements, indexed 0..n-1).
5//! 2. Single binary relation R with tuples: for each edge {u,v}∈E, include both
6//!    (u,v) and (v,u). So 2|E| tuples, each of arity 2.
7//! 3. Query: k existential variables, with conjuncts R(y_i, y_j) for all 0≤i<j<k.
8//!    That's k*(k-1)/2 conjuncts.
9//! 4. G has a k-clique if and only if the query evaluates to true.
10
11use crate::models::graph::KClique;
12use crate::models::misc::{CbqRelation, ConjunctiveBooleanQuery, QueryArg};
13use crate::reduction;
14use crate::rules::traits::{ReduceTo, ReductionResult};
15use crate::topology::{Graph, SimpleGraph};
16
17/// Result of reducing KClique to ConjunctiveBooleanQuery.
18#[derive(Debug, Clone)]
19pub struct ReductionKCliqueToCBQ {
20    target: ConjunctiveBooleanQuery,
21    num_vertices: usize,
22}
23
24impl ReductionResult for ReductionKCliqueToCBQ {
25    type Source = KClique<SimpleGraph>;
26    type Target = ConjunctiveBooleanQuery;
27
28    fn target_problem(&self) -> &ConjunctiveBooleanQuery {
29        &self.target
30    }
31
32    /// Extract solution from CBQ back to KClique.
33    ///
34    /// CBQ config: vec of length k, each value is a domain element (vertex index).
35    /// KClique config: binary vec of length n; set config[v]=1 for each v in
36    /// the CBQ assignment.
37    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
38        KClique::<SimpleGraph>::config_from_vertices(self.num_vertices, target_solution)
39    }
40}
41
42#[reduction(
43    overhead = {
44        domain_size = "num_vertices",
45        num_relations = "1",
46        num_variables = "k",
47        num_conjuncts = "k * (k - 1) / 2",
48    }
49)]
50impl ReduceTo<ConjunctiveBooleanQuery> for KClique<SimpleGraph> {
51    type Result = ReductionKCliqueToCBQ;
52
53    fn reduce_to(&self) -> Self::Result {
54        let n = self.num_vertices();
55        let k = self.k();
56
57        // Build the single binary relation: for each edge {u,v}, include (u,v) and (v,u).
58        let mut tuples = Vec::with_capacity(self.num_edges() * 2);
59        for (u, v) in self.graph().edges() {
60            tuples.push(vec![u, v]);
61            tuples.push(vec![v, u]);
62        }
63        let relation = CbqRelation { arity: 2, tuples };
64
65        // Build conjuncts: R(y_i, y_j) for all 0 <= i < j < k.
66        let mut conjuncts = Vec::with_capacity(k * k.saturating_sub(1) / 2);
67        for i in 0..k {
68            for j in (i + 1)..k {
69                conjuncts.push((0, vec![QueryArg::Variable(i), QueryArg::Variable(j)]));
70            }
71        }
72
73        let target = ConjunctiveBooleanQuery::new(n, vec![relation], k, conjuncts);
74
75        ReductionKCliqueToCBQ {
76            target,
77            num_vertices: n,
78        }
79    }
80}
81
82#[cfg(feature = "example-db")]
83pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
84    use crate::export::SolutionPair;
85
86    vec![crate::example_db::specs::RuleExampleSpec {
87        id: "kclique_to_conjunctivebooleanquery",
88        build: || {
89            // Triangle (0,1,2) in a 5-vertex graph, k=3 → has 3-clique
90            let source = KClique::new(
91                SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)]),
92                3,
93            );
94            crate::example_db::specs::rule_example_with_witness::<_, ConjunctiveBooleanQuery>(
95                source,
96                SolutionPair {
97                    source_config: vec![1, 1, 1, 0, 0],
98                    target_config: vec![0, 1, 2],
99                },
100            )
101        },
102    }]
103}
104
105#[cfg(test)]
106#[path = "../unit_tests/rules/kclique_conjunctivebooleanquery.rs"]
107mod tests;
problemreductions/rules/kclique_conjunctivebooleanquery.rs

problemreductions/rules/
kclique_conjunctivebooleanquery.rs
