problemreductions/rules/
rootedtreearrangement_rootedtreestorageassignment.rs

1//! Reduction from RootedTreeArrangement to RootedTreeStorageAssignment.
2//!
3//! Given a RootedTreeArrangement instance with graph G = (V, E) and bound K,
4//! construct a RootedTreeStorageAssignment instance:
5//! - Universe X = V (the vertex set)
6//! - For each edge {u, v} in E, create a 2-element subset {u, v}
7//! - Bound K' = K - |E|
8//!
9//! The extension cost for a single edge subset {u,v} equals d_T(u,v) - 1
10//! in the rooted tree, so total extension cost = total arrangement cost - |E|.
11
12use crate::models::graph::RootedTreeArrangement;
13use crate::models::set::RootedTreeStorageAssignment;
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16use crate::topology::{Graph, SimpleGraph};
17
18/// Result of reducing RootedTreeArrangement to RootedTreeStorageAssignment.
19#[derive(Debug, Clone)]
20pub struct ReductionRootedTreeArrangementToRootedTreeStorageAssignment {
21    target: RootedTreeStorageAssignment,
22    /// Number of vertices in the source graph (needed for solution extraction).
23    num_vertices: usize,
24}
25
26impl ReductionResult for ReductionRootedTreeArrangementToRootedTreeStorageAssignment {
27    type Source = RootedTreeArrangement<SimpleGraph>;
28    type Target = RootedTreeStorageAssignment;
29
30    fn target_problem(&self) -> &Self::Target {
31        &self.target
32    }
33
34    /// Extract a source solution from a target solution.
35    ///
36    /// The target config is a parent array defining a rooted tree on X = V.
37    /// The source config is [parent_array | identity_mapping] since X = V
38    /// means the mapping f is the identity.
39    fn extract_solution(
40        &self,
41        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
42    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
43        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
44
45        Ok({
46            let n = self.num_vertices;
47            // target_solution is the parent array of the rooted tree on X = V
48            // Source config = [parent_array, identity_mapping]
49            let mut source_config = target_solution.to_vec();
50            // Append identity mapping: f(v) = v for all v
51            source_config.extend(0..n);
52            source_config
53        })
54    }
55}
56
57#[reduction(
58    transform = exact {
59        universe_size = "num_vertices",
60        num_subsets = "num_edges",
61    }
62)]
63impl ReduceTo<RootedTreeStorageAssignment> for RootedTreeArrangement<SimpleGraph> {
64    type Result = ReductionRootedTreeArrangementToRootedTreeStorageAssignment;
65
66    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
67        let n = self.num_vertices();
68        let edges = self.graph().edges();
69        let num_edges = edges.len();
70
71        // Each edge becomes a 2-element subset
72        let subsets: Vec<Vec<usize>> = edges.iter().map(|&(u, v)| vec![u, v]).collect();
73
74        // Bound K' = K - |E|. If this underflows (K < |E|), the source instance
75        // is infeasible (each edge contributes at least 1 to the arrangement
76        // cost). In that case, return a fixed gadget instance that is
77        // guaranteed infeasible for the target problem as well.
78        let num_edges = i64::try_from(num_edges).map_err(|_| {
79            crate::rules::ReductionError::integer_overflow::<
80                RootedTreeArrangement<SimpleGraph>,
81                RootedTreeStorageAssignment,
82            >("converting the number of edges to i64")
83        })?;
84        let bound = match self.bound().checked_sub(num_edges) {
85            Some(b) => b,
86            None => {
87                // Gadget: universe {0,1,2} with all 2-element subsets and bound 0.
88                // For any rooted tree on three vertices, at least one pair has
89                // distance 2, so at least one subset has extension cost >= 1.
90                // Thus the minimum total extension cost is >= 1, making this
91                // instance infeasible for bound 0.
92                let gadget_n = 3;
93                let gadget_subsets = vec![vec![0, 1], vec![1, 2], vec![0, 2]];
94                let target = RootedTreeStorageAssignment::new(gadget_n, gadget_subsets, 0);
95
96                return Ok(
97                    ReductionRootedTreeArrangementToRootedTreeStorageAssignment {
98                        target,
99                        num_vertices: gadget_n,
100                    },
101                );
102            }
103        };
104
105        let target = RootedTreeStorageAssignment::new(n, subsets, bound);
106
107        Ok(
108            ReductionRootedTreeArrangementToRootedTreeStorageAssignment {
109                target,
110                num_vertices: n,
111            },
112        )
113    }
114}
115
116#[cfg(feature = "example-db")]
117pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
118    use crate::export::SolutionPair;
119
120    vec![crate::example_db::specs::RuleExampleSpec {
121        id: "rootedtreearrangement_to_rootedtreestorageassignment",
122        build: || {
123            // Path graph P4: 0-1-2-3, bound K=5
124            // Optimal tree: chain 0->1->2->3 (root=0), identity mapping
125            // Total distance = 1+1+1 = 3 <= 5
126            // Target: universe_size=4, subsets={{0,1},{1,2},{2,3}}, bound=5-3=2
127            // Target tree: parent=[0,0,1,2], identity mapping
128            // Extension cost = 0+0+0 = 0 <= 2
129            let source =
130                RootedTreeArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]), 5);
131            let source_config = vec![0, 0, 1, 2, 0, 1, 2, 3];
132            let target_config = vec![0, 0, 1, 2];
133            crate::example_db::specs::rule_example_with_witness::<_, RootedTreeStorageAssignment>(
134                source,
135                SolutionPair {
136                    source_config: serde_json::to_value(source_config)
137                        .expect("solution serialization must succeed"),
138                    target_config: serde_json::to_value(target_config)
139                        .expect("solution serialization must succeed"),
140                },
141            )
142        },
143    }]
144}
145
146#[cfg(test)]
147#[path = "../unit_tests/rules/rootedtreearrangement_rootedtreestorageassignment.rs"]
148mod tests;
problemreductions/rules/rootedtreearrangement_rootedtreestorageassignment.rs

problemreductions/rules/
rootedtreearrangement_rootedtreestorageassignment.rs
