problemreductions/rules/
partitionintopathsoflength2_boundedcomponentspanningforest.rs

1//! Reduction from PartitionIntoPathsOfLength2 to BoundedComponentSpanningForest.
2//!
3//! Given a PartitionIntoPathsOfLength2 instance with graph G = (V, E), |V| = 3q,
4//! construct a BoundedComponentSpanningForest instance on the same graph with
5//! unit vertex weights, K = q = |V|/3 components, and B = 3.
6//!
7//! A valid P3-partition (each triple induces at least 2 edges, hence is connected)
8//! directly corresponds to a bounded-component partition with at most q components
9//! of weight at most 3.
10//!
11//! Reference: Garey & Johnson, ND10, p.208; Hadlock (1974).
12
13use crate::models::graph::{BoundedComponentSpanningForest, PartitionIntoPathsOfLength2};
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16use crate::topology::{Graph, SimpleGraph};
17
18/// Result of reducing PartitionIntoPathsOfLength2 to BoundedComponentSpanningForest.
19#[derive(Debug, Clone)]
20pub struct ReductionPPL2ToBCSF {
21    target: BoundedComponentSpanningForest<SimpleGraph, i32>,
22}
23
24impl ReductionResult for ReductionPPL2ToBCSF {
25    type Source = PartitionIntoPathsOfLength2<SimpleGraph>;
26    type Target = BoundedComponentSpanningForest<SimpleGraph, i32>;
27
28    fn target_problem(&self) -> &Self::Target {
29        &self.target
30    }
31
32    /// Extract source solution from target solution.
33    ///
34    /// Both problems use the same vertex-to-group assignment encoding,
35    /// so the solution mapping is identity.
36    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
37        target_solution.to_vec()
38    }
39}
40
41#[reduction(
42    overhead = {
43        num_vertices = "num_vertices",
44        num_edges = "num_edges",
45        max_components = "num_vertices / 3",
46    }
47)]
48impl ReduceTo<BoundedComponentSpanningForest<SimpleGraph, i32>>
49    for PartitionIntoPathsOfLength2<SimpleGraph>
50{
51    type Result = ReductionPPL2ToBCSF;
52
53    fn reduce_to(&self) -> Self::Result {
54        let n = self.num_vertices();
55        let q = n / 3;
56
57        // Handle empty graph: max_components must be >= 1
58        let max_components = if q == 0 { 1 } else { q };
59
60        let target = BoundedComponentSpanningForest::new(
61            SimpleGraph::new(n, self.graph().edges()),
62            vec![1i32; n],  // unit weights
63            max_components, // K = max(|V|/3, 1)
64            3,              // B = 3
65        );
66
67        ReductionPPL2ToBCSF { target }
68    }
69}
70
71#[cfg(feature = "example-db")]
72pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
73    use crate::export::SolutionPair;
74
75    vec![crate::example_db::specs::RuleExampleSpec {
76        id: "partitionintopathsoflength2_to_boundedcomponentspanningforest",
77        build: || {
78            // 6-vertex graph with two P3 paths: 0-1-2 and 3-4-5
79            let source = PartitionIntoPathsOfLength2::new(SimpleGraph::new(
80                6,
81                vec![(0, 1), (1, 2), (3, 4), (4, 5)],
82            ));
83            crate::example_db::specs::rule_example_with_witness::<
84                _,
85                BoundedComponentSpanningForest<SimpleGraph, i32>,
86            >(
87                source,
88                SolutionPair {
89                    source_config: vec![0, 0, 0, 1, 1, 1],
90                    target_config: vec![0, 0, 0, 1, 1, 1],
91                },
92            )
93        },
94    }]
95}
96
97#[cfg(test)]
98#[path = "../unit_tests/rules/partitionintopathsoflength2_boundedcomponentspanningforest.rs"]
99mod tests;
problemreductions/rules/partitionintopathsoflength2_boundedcomponentspanningforest.rs

problemreductions/rules/
partitionintopathsoflength2_boundedcomponentspanningforest.rs
