problemreductions/rules/
prizecollectingsteinerforest_steinertree.rs

1//! Reduction from Prize-Collecting Steiner Forest (PCSF) to Steiner Tree
2//! via the artificial-root + per-vertex prize gadget construction.
3//!
4//! The PCSF objective on `(V, E)` with vertex prizes `p`, edge costs `c`,
5//! tradeoff `beta`, and per-component penalty `omega` is
6//!
7//! ```text
8//! beta * sum_{v notin V_F} p(v) + sum_{e in E_F} c(e) + omega * kappa(F).
9//! ```
10//!
11//! We build a Steiner-tree instance on the augmented graph
12//! `H = (V cup {r} cup {t_v : v in V_p}, E_H)` where `V_p` collects the
13//! vertices with `p(v) > 0`, and
14//!
15//! - every original edge keeps its cost,
16//! - every `v in V` is attached to `r` by an edge of cost `omega` (so each
17//!   tree component of `F` is paid by exactly one root-attachment edge in
18//!   `T*`),
19//! - for every `v in V_p` we add `(v, t_v)` of cost `0` and `(r, t_v)` of
20//!   cost `beta * p(v)`,
21//! - the terminal set is `{r} cup {t_v : v in V_p}`.
22//!
23//! The Steiner-tree optimum then equals the PCSF optimum.
24//!
25//! References:
26//! - Bienstock, Goemans, Simchi-Levi, Williamson, "A note on the prize
27//!   collecting traveling salesman problem," Math. Programming 59 (1993).
28//!   <https://doi.org/10.1007/BF01581256>
29//! - Tuncbag et al., "Simultaneous Reconstruction of Multiple Signaling
30//!   Pathways via the Prize-Collecting Steiner Forest Problem,"
31//!   J. Comput. Biol. 20(2):124--136, 2013.
32//!   <https://doi.org/10.1089/cmb.2012.0092>
33
34use crate::models::graph::{PrizeCollectingSteinerForest, SteinerTree};
35use crate::reduction;
36use crate::rules::traits::{ReduceTo, ReductionResult};
37use crate::topology::{Graph, SimpleGraph};
38
39/// Result of reducing PCSF to SteinerTree.
40///
41/// Stores the original PCSF source sizes plus the mapping from the target
42/// graph's edge list back to the source variables (the original edge index
43/// for each "original" edge, and the source vertex index for each gadget
44/// include-edge). Other target edges (root-attachment and gadget omit-edges)
45/// are not needed for extraction.
46#[derive(Debug, Clone)]
47pub struct ReductionPCSFToSteinerTree {
48    target: SteinerTree<SimpleGraph, i32>,
49    /// Number of vertices in the source graph (also the prefix size of the
50    /// source configuration's vertex-selector segment).
51    num_source_vertices: usize,
52    /// Number of edges in the source graph (length of the edge-selector
53    /// segment of the source configuration).
54    num_source_edges: usize,
55    /// `target_to_source_edge[i] = Some(j)` iff target edge `i` is the same
56    /// pair as source edge `j`; otherwise the target edge is a gadget edge.
57    target_to_source_edge: Vec<Option<usize>>,
58    /// `target_to_include_vertex[i] = Some(v)` iff target edge `i` is the
59    /// include-edge `(v, t_v)` of the per-vertex prize gadget. Original
60    /// edges and other gadget edges store `None`.
61    target_to_include_vertex: Vec<Option<usize>>,
62}
63
64impl ReductionResult for ReductionPCSFToSteinerTree {
65    type Source = PrizeCollectingSteinerForest<SimpleGraph, i32>;
66    type Target = SteinerTree<SimpleGraph, i32>;
67
68    fn target_problem(&self) -> &SteinerTree<SimpleGraph, i32> {
69        &self.target
70    }
71
72    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
73        let n = self.num_source_vertices;
74        let m = self.num_source_edges;
75        let mut source_config = vec![0usize; n + m];
76
77        // Mark vertices included via their gadget include-edge `(v, t_v)`,
78        // and edges via the matching original edge.
79        for (target_idx, &selected) in target_solution.iter().enumerate() {
80            if selected != 1 {
81                continue;
82            }
83            if let Some(v) = self.target_to_include_vertex[target_idx] {
84                source_config[v] = 1;
85            } else if let Some(src_edge) = self.target_to_source_edge[target_idx] {
86                source_config[n + src_edge] = 1;
87            }
88        }
89
90        // Any original edge selected in `T*` forces both endpoints into
91        // `V_F`. The PCSF model rejects configurations where a selected
92        // edge has an unselected endpoint, so we mark endpoints explicitly
93        // (this also covers prize-zero endpoints, which have no gadget).
94        let edges = self.target.graph().edges();
95        for (target_idx, &(_, _)) in edges.iter().enumerate() {
96            if target_solution.get(target_idx).copied() != Some(1) {
97                continue;
98            }
99            if let Some(src_edge) = self.target_to_source_edge[target_idx] {
100                let (u, v) = self.source_edge_pair(src_edge);
101                source_config[u] = 1;
102                source_config[v] = 1;
103            }
104        }
105
106        source_config
107    }
108}
109
110impl ReductionPCSFToSteinerTree {
111    /// Look up the endpoint pair of the `idx`-th source edge in the target
112    /// graph's edge list (source edges are placed first by construction).
113    fn source_edge_pair(&self, src_edge_idx: usize) -> (usize, usize) {
114        self.target.graph().edges()[src_edge_idx]
115    }
116}
117
118#[reduction(
119    overhead = {
120        num_vertices = "num_vertices + num_vertices_with_prize + 1",
121        num_edges = "num_edges + num_vertices + 2 * num_vertices_with_prize",
122        num_terminals = "num_vertices_with_prize + 1",
123    }
124)]
125impl ReduceTo<SteinerTree<SimpleGraph, i32>> for PrizeCollectingSteinerForest<SimpleGraph, i32> {
126    type Result = ReductionPCSFToSteinerTree;
127
128    fn reduce_to(&self) -> Self::Result {
129        let n = self.num_vertices();
130        let m = self.num_edges();
131        let source_edges = self.graph().edges();
132        let source_edge_costs = self.edge_costs();
133        let source_prizes = self.vertex_prizes();
134        let beta = *self.beta();
135        let omega = *self.omega();
136
137        // Augmented vertex layout:
138        //   indices 0..n           -- original vertices
139        //   index   n               -- artificial root r
140        //   indices n+1..n+1+k      -- gadget terminals t_v for v in V_p,
141        //                              listed in increasing order of v.
142        let prized: Vec<usize> = (0..n).filter(|&v| source_prizes[v] > 0).collect();
143        let k = prized.len();
144        let root = n;
145        let gadget_terminal = |gadget_pos: usize| -> usize { n + 1 + gadget_pos };
146
147        let target_num_vertices = n + 1 + k;
148        let mut target_edges: Vec<(usize, usize)> = Vec::with_capacity(m + n + 2 * k);
149        let mut target_edge_weights: Vec<i32> = Vec::with_capacity(m + n + 2 * k);
150        let mut target_to_source_edge: Vec<Option<usize>> = Vec::with_capacity(m + n + 2 * k);
151        let mut target_to_include_vertex: Vec<Option<usize>> = Vec::with_capacity(m + n + 2 * k);
152
153        // 1. Original edges keep their cost.
154        for (idx, &(u, v)) in source_edges.iter().enumerate() {
155            target_edges.push((u, v));
156            target_edge_weights.push(source_edge_costs[idx]);
157            target_to_source_edge.push(Some(idx));
158            target_to_include_vertex.push(None);
159        }
160
161        // 2. Root-attachment edge (r, v) of cost omega for every v in V.
162        for v in 0..n {
163            target_edges.push((v, root));
164            target_edge_weights.push(omega);
165            target_to_source_edge.push(None);
166            target_to_include_vertex.push(None);
167        }
168
169        // 3. Per-prized-vertex gadget: (v, t_v) of cost 0 and (r, t_v) of
170        // cost beta * p(v).
171        for (gadget_pos, &v) in prized.iter().enumerate() {
172            let t_v = gadget_terminal(gadget_pos);
173            // include-edge: marks "v is in V_F" with cost 0.
174            target_edges.push((v, t_v));
175            target_edge_weights.push(0);
176            target_to_source_edge.push(None);
177            target_to_include_vertex.push(Some(v));
178            // omit-edge: pays beta * p(v) when v is excluded from V_F.
179            target_edges.push((root, t_v));
180            target_edge_weights.push(beta * source_prizes[v]);
181            target_to_source_edge.push(None);
182            target_to_include_vertex.push(None);
183        }
184
185        // 4. Terminal set: r plus every gadget terminal t_v.
186        let mut terminals: Vec<usize> = Vec::with_capacity(k + 1);
187        terminals.push(root);
188        for gadget_pos in 0..k {
189            terminals.push(gadget_terminal(gadget_pos));
190        }
191
192        let target_graph = SimpleGraph::new(target_num_vertices, target_edges);
193        let target =
194            SteinerTree::<SimpleGraph, i32>::new(target_graph, target_edge_weights, terminals);
195
196        ReductionPCSFToSteinerTree {
197            target,
198            num_source_vertices: n,
199            num_source_edges: m,
200            target_to_source_edge,
201            target_to_include_vertex,
202        }
203    }
204}
205
206#[cfg(feature = "example-db")]
207pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
208    use crate::example_db::specs::RuleExampleSpec;
209    use crate::export::SolutionPair;
210    use crate::solvers::BruteForce;
211
212    vec![RuleExampleSpec {
213        id: "prize_collecting_steiner_forest_to_steiner_tree",
214        build: || {
215            // Issue #1027 canonical instance with the omit-edge actually
216            // selected at the optimum: path 0 - 1 - 2 with c(0,1)=10,
217            // c(1,2)=10, prizes p = (5, 1, 5), beta = 1, omega = 1. The
218            // optimum drops vertex 1 (paying p(1) = 1) rather than paying a
219            // size-10 edge to reach it.
220            let source = PrizeCollectingSteinerForest::<SimpleGraph, i32>::new(
221                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
222                vec![5, 1, 5],
223                vec![10, 10],
224                1,
225                1,
226            );
227            let reduction = <PrizeCollectingSteinerForest<SimpleGraph, i32> as ReduceTo<
228                SteinerTree<SimpleGraph, i32>,
229            >>::reduce_to(&source);
230            let target = reduction.target_problem();
231            let target_config = BruteForce::new()
232                .find_witness(target)
233                .expect("canonical PCSF -> SteinerTree example must have an optimal target tree");
234            let source_config = reduction.extract_solution(&target_config);
235            crate::example_db::specs::assemble_rule_example(
236                &source,
237                target,
238                vec![SolutionPair {
239                    source_config,
240                    target_config,
241                }],
242            )
243        },
244    }]
245}
246
247#[cfg(test)]
248#[path = "../unit_tests/rules/prizecollectingsteinerforest_steinertree.rs"]
249mod tests;
problemreductions/rules/prizecollectingsteinerforest_steinertree.rs

problemreductions/rules/
prizecollectingsteinerforest_steinertree.rs
