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    /// the source selection is the negation of the target's left-side selection.
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_solution(self.target_problem(), target_solution)?;
42
43        Ok({
44            (0..self.num_original_vertices)
45                .map(|v| !target_solution[v])
46                .collect()
47        })
48    }
49}
50
51#[reduction(
52    transform = exact {
53        left_size = "num_vertices + k * (k - 1) / 2",
54        right_size = "num_edges + num_vertices - k",
55        k = "num_vertices + k * (k - 1) / 2 - k",
56    },
57    unavailable = {
58        num_vertices = "the exact target parameter is not represented by this reduction's symbolic transform",
59    }
60)]
61impl ReduceTo<BalancedCompleteBipartiteSubgraph> for KClique<SimpleGraph> {
62    type Result = ReductionKCliqueToBCBS;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let n = self.num_vertices();
66        let k = self.k();
67        let edges: Vec<(usize, usize)> = self.graph().edges();
68        let m = edges.len();
69
70        // C(k, 2) = k*(k-1)/2 — number of edges in a k-clique
71        let ck2 = k * (k - 1) / 2;
72
73        // Part A (left partition): n' = n + C(k,2) vertices
74        let left_size = n + ck2;
75
76        // Part B (right partition): m edge elements + (n - k) padding elements
77        let num_padding = n - k;
78        let right_size = m + num_padding;
79
80        // Target biclique parameter: K' = n' - k
81        let target_k = left_size - k;
82
83        // Build bipartite edges using non-incidence encoding
84        let mut bip_edges = Vec::new();
85
86        for v in 0..left_size {
87            // Edge elements: add edge (v, j) if v is NOT an endpoint of edges[j]
88            for (j, &(u, w)) in edges.iter().enumerate() {
89                if v != u && v != w {
90                    // For padded vertices (v >= n), they are never endpoints
91                    // of any original edge, so they always connect.
92                    bip_edges.push((v, j));
93                }
94            }
95
96            // Padding elements: always connected
97            for p in 0..num_padding {
98                bip_edges.push((v, m + p));
99            }
100        }
101
102        let graph = BipartiteGraph::new(left_size, right_size, bip_edges);
103        let target = BalancedCompleteBipartiteSubgraph::new(graph, target_k);
104
105        Ok(ReductionKCliqueToBCBS {
106            target,
107            num_original_vertices: n,
108        })
109    }
110}
111
112#[cfg(feature = "example-db")]
113pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
114    use crate::export::SolutionPair;
115
116    vec![crate::example_db::specs::RuleExampleSpec {
117        id: "kclique_to_balancedcompletebipartitesubgraph",
118        build: || {
119            // 4-vertex graph with edges {0,1}, {0,2}, {1,2}, {2,3}, k=3
120            // Known 3-clique: {0, 1, 2}
121            let source = KClique::new(SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (2, 3)]), 3);
122            // Source config: vertices {0,1,2} selected = [1,1,1,0]
123            // Target: left_size=7, right_size=5, k'=4
124            // Left side: NOT selecting clique vertices -> select {3,4,5,6}
125            // target_config for left: [0,0,0,1,1,1,1]
126            // Right side: select edge elements for clique edges + padding
127            //   e0={0,1}, e1={0,2}, e2={1,2} are clique edges -> select them
128            //   e3={2,3} is not a clique edge -> don't select
129            //   w0 is padding -> select
130            // target_config for right: [1,1,1,0,1]
131            // Full target config: [0,0,0,1,1,1,1, 1,1,1,0,1]
132            crate::example_db::specs::rule_example_with_witness::<
133                _,
134                BalancedCompleteBipartiteSubgraph,
135            >(
136                source,
137                SolutionPair {
138                    source_config: serde_json::json!(vec![true, true, true, false]),
139                    target_config: serde_json::json!(vec![
140                        false, false, false, true, true, true, true, true, true, true, false, true
141                    ]),
142                },
143            )
144        },
145    }]
146}
147
148#[cfg(test)]
149#[path = "../unit_tests/rules/kclique_balancedcompletebipartitesubgraph.rs"]
150mod tests;
problemreductions/rules/kclique_balancedcompletebipartitesubgraph.rs

problemreductions/rules/
kclique_balancedcompletebipartitesubgraph.rs
