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, i64>,
22}
23
24impl ReductionResult for ReductionPPL2ToBCSF {
25    type Source = PartitionIntoPathsOfLength2<SimpleGraph>;
26    type Target = BoundedComponentSpanningForest<SimpleGraph, i64>;
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(
37        &self,
38        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
39    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
40        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
41
42        Ok(target_solution.to_vec())
43    }
44}
45
46#[reduction(
47    transform = exact {
48        num_vertices = "num_vertices",
49        num_edges = "num_edges",
50        max_components = "num_vertices / 3",
51    }
52)]
53impl ReduceTo<BoundedComponentSpanningForest<SimpleGraph, i64>>
54    for PartitionIntoPathsOfLength2<SimpleGraph>
55{
56    type Result = ReductionPPL2ToBCSF;
57
58    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
59        let n = self.num_vertices();
60        let q = n / 3;
61
62        // Handle empty graph: max_components must be >= 1
63        let max_components = if q == 0 { 1 } else { q };
64
65        let target = BoundedComponentSpanningForest::new(
66            SimpleGraph::new(n, self.graph().edges()),
67            vec![1i64; n],  // unit weights
68            max_components, // K = max(|V|/3, 1)
69            3,              // B = 3
70        );
71
72        Ok(ReductionPPL2ToBCSF { target })
73    }
74}
75
76#[cfg(feature = "example-db")]
77pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
78    use crate::export::SolutionPair;
79
80    vec![crate::example_db::specs::RuleExampleSpec {
81        id: "partitionintopathsoflength2_to_boundedcomponentspanningforest",
82        build: || {
83            // 6-vertex graph with two P3 paths: 0-1-2 and 3-4-5
84            let source = PartitionIntoPathsOfLength2::new(SimpleGraph::new(
85                6,
86                vec![(0, 1), (1, 2), (3, 4), (4, 5)],
87            ));
88            crate::example_db::specs::rule_example_with_witness::<
89                _,
90                BoundedComponentSpanningForest<SimpleGraph, i64>,
91            >(
92                source,
93                SolutionPair {
94                    source_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
95                    target_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
96                },
97            )
98        },
99    }]
100}
101
102#[cfg(test)]
103#[path = "../unit_tests/rules/partitionintopathsoflength2_boundedcomponentspanningforest.rs"]
104mod tests;
problemreductions/rules/partitionintopathsoflength2_boundedcomponentspanningforest.rs

problemreductions/rules/
partitionintopathsoflength2_boundedcomponentspanningforest.rs
