problemreductions/rules/
kclique_balancedcompletebipartitesubgraph.rs

1//! Reduction from KClique to BalancedCompleteBipartiteSubgraph.
2//!
3//! Classical reduction attributed to Garey and Johnson (GT24) and published in
4//! Johnson (1987). Given a KClique instance (G, k), constructs a bipartite graph
5//! where Part A = padded vertex set and Part B = edge elements + padding elements,
6//! with non-incidence adjacency encoding.
7
8use crate::models::graph::{BalancedCompleteBipartiteSubgraph, KClique};
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{BipartiteGraph, Graph, SimpleGraph};
12
13/// Result of reducing KClique to BalancedCompleteBipartiteSubgraph.
14///
15/// Stores the target problem and the number of original vertices for
16/// solution extraction.
17#[derive(Debug, Clone)]
18pub struct ReductionKCliqueToBCBS {
19    target: BalancedCompleteBipartiteSubgraph,
20    /// Number of vertices in the original graph (before padding).
21    num_original_vertices: usize,
22}
23
24impl ReductionResult for ReductionKCliqueToBCBS {
25    type Source = KClique<SimpleGraph>;
26    type Target = BalancedCompleteBipartiteSubgraph;
27
28    fn target_problem(&self) -> &BalancedCompleteBipartiteSubgraph {
29        &self.target
30    }
31
32    /// Extract KClique solution from BalancedCompleteBipartiteSubgraph solution.
33    ///
34    /// The k-clique is S = {v in V : v not in A'}, i.e., the original vertices
35    /// NOT selected on the left side. For each original vertex v (0..n-1):
36    /// source_config[v] = 1 - target_config[v].
37    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
38        (0..self.num_original_vertices)
39            .map(|v| 1 - target_solution[v])
40            .collect()
41    }
42}
43
44#[reduction(
45    overhead = {
46        left_size = "num_vertices + k * (k - 1) / 2",
47        right_size = "num_edges + num_vertices - k",
48        k = "num_vertices + k * (k - 1) / 2 - k",
49    }
50)]
51impl ReduceTo<BalancedCompleteBipartiteSubgraph> for KClique<SimpleGraph> {
52    type Result = ReductionKCliqueToBCBS;
53
54    fn reduce_to(&self) -> Self::Result {
55        let n = self.num_vertices();
56        let k = self.k();
57        let edges: Vec<(usize, usize)> = self.graph().edges();
58        let m = edges.len();
59
60        // C(k, 2) = k*(k-1)/2 — number of edges in a k-clique
61        let ck2 = k * (k - 1) / 2;
62
63        // Part A (left partition): n' = n + C(k,2) vertices
64        let left_size = n + ck2;
65
66        // Part B (right partition): m edge elements + (n - k) padding elements
67        let num_padding = n - k;
68        let right_size = m + num_padding;
69
70        // Target biclique parameter: K' = n' - k
71        let target_k = left_size - k;
72
73        // Build bipartite edges using non-incidence encoding
74        let mut bip_edges = Vec::new();
75
76        for v in 0..left_size {
77            // Edge elements: add edge (v, j) if v is NOT an endpoint of edges[j]
78            for (j, &(u, w)) in edges.iter().enumerate() {
79                if v != u && v != w {
80                    // For padded vertices (v >= n), they are never endpoints
81                    // of any original edge, so they always connect.
82                    bip_edges.push((v, j));
83                }
84            }
85
86            // Padding elements: always connected
87            for p in 0..num_padding {
88                bip_edges.push((v, m + p));
89            }
90        }
91
92        let graph = BipartiteGraph::new(left_size, right_size, bip_edges);
93        let target = BalancedCompleteBipartiteSubgraph::new(graph, target_k);
94
95        ReductionKCliqueToBCBS {
96            target,
97            num_original_vertices: n,
98        }
99    }
100}
101
102#[cfg(feature = "example-db")]
103pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
104    use crate::export::SolutionPair;
105
106    vec![crate::example_db::specs::RuleExampleSpec {
107        id: "kclique_to_balancedcompletebipartitesubgraph",
108        build: || {
109            // 4-vertex graph with edges {0,1}, {0,2}, {1,2}, {2,3}, k=3
110            // Known 3-clique: {0, 1, 2}
111            let source = KClique::new(SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (2, 3)]), 3);
112            // Source config: vertices {0,1,2} selected = [1,1,1,0]
113            // Target: left_size=7, right_size=5, k'=4
114            // Left side: NOT selecting clique vertices -> select {3,4,5,6}
115            // target_config for left: [0,0,0,1,1,1,1]
116            // Right side: select edge elements for clique edges + padding
117            //   e0={0,1}, e1={0,2}, e2={1,2} are clique edges -> select them
118            //   e3={2,3} is not a clique edge -> don't select
119            //   w0 is padding -> select
120            // target_config for right: [1,1,1,0,1]
121            // Full target config: [0,0,0,1,1,1,1, 1,1,1,0,1]
122            crate::example_db::specs::rule_example_with_witness::<
123                _,
124                BalancedCompleteBipartiteSubgraph,
125            >(
126                source,
127                SolutionPair {
128                    source_config: vec![1, 1, 1, 0],
129                    target_config: vec![0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
130                },
131            )
132        },
133    }]
134}
135
136#[cfg(test)]
137#[path = "../unit_tests/rules/kclique_balancedcompletebipartitesubgraph.rs"]
138mod tests;
problemreductions/rules/kclique_balancedcompletebipartitesubgraph.rs

problemreductions/rules/
kclique_balancedcompletebipartitesubgraph.rs
