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(&self, target_solution: &[usize]) -> Vec<usize> {
40        let n = self.num_vertices;
41        // target_solution is the parent array of the rooted tree on X = V
42        // Source config = [parent_array, identity_mapping]
43        let mut source_config = target_solution.to_vec();
44        // Append identity mapping: f(v) = v for all v
45        source_config.extend(0..n);
46        source_config
47    }
48}
49
50#[reduction(
51    overhead = {
52        universe_size = "num_vertices",
53        num_subsets = "num_edges",
54    }
55)]
56impl ReduceTo<RootedTreeStorageAssignment> for RootedTreeArrangement<SimpleGraph> {
57    type Result = ReductionRootedTreeArrangementToRootedTreeStorageAssignment;
58
59    fn reduce_to(&self) -> Self::Result {
60        let n = self.num_vertices();
61        let edges = self.graph().edges();
62        let num_edges = edges.len();
63
64        // Each edge becomes a 2-element subset
65        let subsets: Vec<Vec<usize>> = edges.iter().map(|&(u, v)| vec![u, v]).collect();
66
67        // Bound K' = K - |E|. If this underflows (K < |E|), the source instance
68        // is infeasible (each edge contributes at least 1 to the arrangement
69        // cost). In that case, return a fixed gadget instance that is
70        // guaranteed infeasible for the target problem as well.
71        let bound = match self.bound().checked_sub(num_edges) {
72            Some(b) => b,
73            None => {
74                // Gadget: universe {0,1,2} with all 2-element subsets and bound 0.
75                // For any rooted tree on three vertices, at least one pair has
76                // distance 2, so at least one subset has extension cost >= 1.
77                // Thus the minimum total extension cost is >= 1, making this
78                // instance infeasible for bound 0.
79                let gadget_n = 3;
80                let gadget_subsets = vec![vec![0, 1], vec![1, 2], vec![0, 2]];
81                let target = RootedTreeStorageAssignment::new(gadget_n, gadget_subsets, 0);
82
83                return ReductionRootedTreeArrangementToRootedTreeStorageAssignment {
84                    target,
85                    num_vertices: gadget_n,
86                };
87            }
88        };
89
90        let target = RootedTreeStorageAssignment::new(n, subsets, bound);
91
92        ReductionRootedTreeArrangementToRootedTreeStorageAssignment {
93            target,
94            num_vertices: n,
95        }
96    }
97}
98
99#[cfg(feature = "example-db")]
100pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
101    use crate::export::SolutionPair;
102
103    vec![crate::example_db::specs::RuleExampleSpec {
104        id: "rootedtreearrangement_to_rootedtreestorageassignment",
105        build: || {
106            // Path graph P4: 0-1-2-3, bound K=5
107            // Optimal tree: chain 0->1->2->3 (root=0), identity mapping
108            // Total distance = 1+1+1 = 3 <= 5
109            // Target: universe_size=4, subsets={{0,1},{1,2},{2,3}}, bound=5-3=2
110            // Target tree: parent=[0,0,1,2], identity mapping
111            // Extension cost = 0+0+0 = 0 <= 2
112            let source =
113                RootedTreeArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]), 5);
114            let source_config = vec![0, 0, 1, 2, 0, 1, 2, 3];
115            let target_config = vec![0, 0, 1, 2];
116            crate::example_db::specs::rule_example_with_witness::<_, RootedTreeStorageAssignment>(
117                source,
118                SolutionPair {
119                    source_config,
120                    target_config,
121                },
122            )
123        },
124    }]
125}
126
127#[cfg(test)]
128#[path = "../unit_tests/rules/rootedtreearrangement_rootedtreestorageassignment.rs"]
129mod tests;
problemreductions/rules/rootedtreearrangement_rootedtreestorageassignment.rs

problemreductions/rules/
rootedtreearrangement_rootedtreestorageassignment.rs
