problemreductions/rules/
kclique_subgraphisomorphism.rs

1//! Reduction from KClique to SubgraphIsomorphism.
2//!
3//! Given a KClique instance (G, k), we construct a SubgraphIsomorphism instance
4//! where the host graph is G and the pattern graph is K_k (the complete graph on
5//! k vertices). G contains a k-clique if and only if G contains a subgraph
6//! isomorphic to K_k.
7
8use crate::models::graph::{KClique, SubgraphIsomorphism};
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::SimpleGraph;
12
13/// Result of reducing KClique to SubgraphIsomorphism.
14///
15/// The host graph is the original graph G and the pattern graph is K_k.
16/// A subgraph isomorphism mapping f: V(K_k) -> V(G) identifies the k vertices
17/// that form a clique in G.
18#[derive(Debug, Clone)]
19pub struct ReductionKCliqueToSubIso {
20    target: SubgraphIsomorphism,
21    num_source_vertices: usize,
22}
23
24impl ReductionResult for ReductionKCliqueToSubIso {
25    type Source = KClique<SimpleGraph>;
26    type Target = SubgraphIsomorphism;
27
28    fn target_problem(&self) -> &SubgraphIsomorphism {
29        &self.target
30    }
31
32    /// Extract KClique solution from SubgraphIsomorphism solution.
33    ///
34    /// The SubgraphIsomorphism config maps each pattern vertex (0..k-1) to a
35    /// host vertex. We create a binary vector of length n and set positions
36    /// f(0), f(1), ..., f(k-1) to 1.
37    fn extract_solution(
38        &self,
39        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
40    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
41        crate::rules::traits::validate_target_witness(
42            self.target_problem(),
43            target_solution,
44            |value| value.0,
45            "target witness is not satisfying",
46        )?;
47
48        Ok(KClique::<SimpleGraph>::config_from_vertices(
49            self.num_source_vertices,
50            target_solution,
51        ))
52    }
53}
54
55#[crate::aggregate_reduction(identity)]
56impl crate::rules::AggregateReductionResult for ReductionKCliqueToSubIso {}
57
58#[reduction(
59    transform = exact {
60        num_host_vertices = "num_vertices",
61        num_host_edges = "num_edges",
62        num_pattern_vertices = "k",
63        num_pattern_edges = "k * (k - 1) / 2",
64    }
65)]
66impl ReduceTo<SubgraphIsomorphism> for KClique<SimpleGraph> {
67    type Result = ReductionKCliqueToSubIso;
68
69    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
70        let n = self.num_vertices();
71        let k = self.k();
72
73        let pattern = SimpleGraph::complete(k);
74        let host = self.graph().clone();
75
76        let target = SubgraphIsomorphism::new(host, pattern);
77
78        Ok(ReductionKCliqueToSubIso {
79            target,
80            num_source_vertices: n,
81        })
82    }
83}
84
85#[cfg(feature = "example-db")]
86pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
87    use crate::export::SolutionPair;
88
89    vec![crate::example_db::specs::RuleExampleSpec {
90        id: "kclique_to_subgraphisomorphism",
91        build: || {
92            // 5-vertex graph with a known 3-clique on vertices {2, 3, 4}
93            let source = KClique::new(
94                SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
95                3,
96            );
97            crate::example_db::specs::rule_example_with_witness::<_, SubgraphIsomorphism>(
98                source,
99                SolutionPair {
100                    source_config: serde_json::json!(vec![false, false, true, true, true]),
101                    target_config: serde_json::json!(vec![2, 3, 4]),
102                },
103            )
104        },
105    }]
106}
107
108#[cfg(test)]
109#[path = "../unit_tests/rules/kclique_subgraphisomorphism.rs"]
110mod tests;
problemreductions/rules/kclique_subgraphisomorphism.rs

problemreductions/rules/
kclique_subgraphisomorphism.rs
