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

problemreductions/rules/
partitionintopathsoflength2_boundedcomponentspanningforest.rs
