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(&self, target_solution: &[usize]) -> Vec<usize> {
38        KClique::<SimpleGraph>::config_from_vertices(self.num_source_vertices, target_solution)
39    }
40}
41
42#[reduction(
43    overhead = {
44        num_host_vertices = "num_vertices",
45        num_host_edges = "num_edges",
46        num_pattern_vertices = "k",
47        num_pattern_edges = "k * (k - 1) / 2",
48    }
49)]
50impl ReduceTo<SubgraphIsomorphism> for KClique<SimpleGraph> {
51    type Result = ReductionKCliqueToSubIso;
52
53    fn reduce_to(&self) -> Self::Result {
54        let n = self.num_vertices();
55        let k = self.k();
56
57        let pattern = SimpleGraph::complete(k);
58        let host = self.graph().clone();
59
60        let target = SubgraphIsomorphism::new(host, pattern);
61
62        ReductionKCliqueToSubIso {
63            target,
64            num_source_vertices: n,
65        }
66    }
67}
68
69#[cfg(feature = "example-db")]
70pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
71    use crate::export::SolutionPair;
72
73    vec![crate::example_db::specs::RuleExampleSpec {
74        id: "kclique_to_subgraphisomorphism",
75        build: || {
76            // 5-vertex graph with a known 3-clique on vertices {2, 3, 4}
77            let source = KClique::new(
78                SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
79                3,
80            );
81            crate::example_db::specs::rule_example_with_witness::<_, SubgraphIsomorphism>(
82                source,
83                SolutionPair {
84                    source_config: vec![0, 0, 1, 1, 1],
85                    target_config: vec![2, 3, 4],
86                },
87            )
88        },
89    }]
90}
91
92#[cfg(test)]
93#[path = "../unit_tests/rules/kclique_subgraphisomorphism.rs"]
94mod tests;
problemreductions/rules/kclique_subgraphisomorphism.rs

problemreductions/rules/
kclique_subgraphisomorphism.rs
