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//! - with `M = omega + 1`, every `v in V_p` gets `(v, t_v)` of cost `M`
20//!   and `(r, t_v)` of cost `M + beta * p(v)`,
21//! - the terminal set is `{r} cup {t_v : v in V_p}`.
22//!
23//! The Steiner-tree optimum equals the PCSF optimum plus `M * |V_p|`.
24//! Every gadget terminal is a leaf in an optimum: replacing its omit edge
25//! with a root attachment when both gadget edges are selected lowers cost.
26//!
27//! References:
28//! - Bienstock, Goemans, Simchi-Levi, Williamson, "A note on the prize
29//!   collecting traveling salesman problem," Math. Programming 59 (1993).
30//!   <https://doi.org/10.1007/BF01581256>
31//! - Tuncbag et al., "Simultaneous Reconstruction of Multiple Signaling
32//!   Pathways via the Prize-Collecting Steiner Forest Problem,"
33//!   J. Comput. Biol. 20(2):124--136, 2013.
34//!   <https://doi.org/10.1089/cmb.2012.0092>
35
36use crate::models::graph::{PrizeCollectingSteinerForest, SteinerTree};
37use crate::reduction;
38use crate::rules::traits::{ReduceTo, ReductionResult};
39use crate::topology::{Graph, SimpleGraph};
40
41/// Result of reducing PCSF to SteinerTree.
42///
43/// Stores the original PCSF source parameters plus the mapping from the target
44/// graph's edge list back to the source variables (the original edge index
45/// for each "original" edge, and the source vertex index for each gadget
46/// include-edge). Other target edges (root-attachment and gadget omit-edges)
47/// are not needed for extraction.
48#[derive(Debug, Clone)]
49pub struct ReductionPCSFToSteinerTree {
50    target: SteinerTree<SimpleGraph, i64>,
51    /// Number of vertices in the source graph (also the prefix size of the
52    /// source configuration's vertex-selector segment).
53    num_source_vertices: usize,
54    /// Number of edges in the source graph (length of the edge-selector
55    /// segment of the source configuration).
56    num_source_edges: usize,
57    /// `target_to_source_edge[i] = Some(j)` iff target edge `i` is the same
58    /// pair as source edge `j`; otherwise the target edge is a gadget edge.
59    target_to_source_edge: Vec<Option<usize>>,
60    /// `target_to_include_vertex[i] = Some(v)` iff target edge `i` is the
61    /// include-edge `(v, t_v)` of the per-vertex prize gadget. Original
62    /// edges and other gadget edges store `None`.
63    target_to_include_vertex: Vec<Option<usize>>,
64}
65
66impl ReductionResult for ReductionPCSFToSteinerTree {
67    type Source = PrizeCollectingSteinerForest<SimpleGraph, i64>;
68    type Target = SteinerTree<SimpleGraph, i64>;
69
70    fn target_problem(&self) -> &SteinerTree<SimpleGraph, i64> {
71        &self.target
72    }
73
74    fn extract_solution(
75        &self,
76        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
77    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
78        crate::rules::traits::validate_target_witness(
79            self.target_problem(),
80            target_solution,
81            |value| value.is_valid(),
82            "target edges do not form a Steiner tree",
83        )?;
84
85        Ok({
86            let n = self.num_source_vertices;
87            let m = self.num_source_edges;
88            let mut selected_vertices = vec![false; n];
89            let mut selected_edges = vec![false; m];
90            let edges = self.target.graph().edges();
91
92            // Mark vertices included via their gadget include-edge `(v, t_v)`,
93            // and edges via the matching original edge.
94            for (target_idx, &selected) in target_solution.iter().enumerate() {
95                if !selected {
96                    continue;
97                }
98                if let Some(v) = self.target_to_include_vertex[target_idx] {
99                    selected_vertices[v] = true;
100                } else if let Some(src_edge) = self.target_to_source_edge[target_idx] {
101                    selected_edges[src_edge] = true;
102                    // Include both endpoints, including prize-zero vertices
103                    // that have no inclusion gadget.
104                    let (u, v) = edges[target_idx];
105                    selected_vertices[u] = true;
106                    selected_vertices[v] = true;
107                }
108            }
109
110            (selected_vertices, selected_edges)
111        })
112    }
113}
114
115#[reduction(
116    transform = exact {
117        num_vertices = "num_vertices + num_vertices_with_prize + 1",
118        num_edges = "num_edges + num_vertices + 2 * num_vertices_with_prize",
119        num_terminals = "num_vertices_with_prize + 1",
120    }
121)]
122impl ReduceTo<SteinerTree<SimpleGraph, i64>> for PrizeCollectingSteinerForest<SimpleGraph, i64> {
123    type Result = ReductionPCSFToSteinerTree;
124
125    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
126        let n = self.num_vertices();
127        let m = self.num_edges();
128        let source_edges = self.graph().edges();
129        let source_edge_costs = self.edge_costs();
130        let source_prizes = self.vertex_prizes();
131        let beta = *self.beta();
132        let omega = *self.omega();
133
134        // Augmented vertex layout:
135        //   indices 0..n           -- original vertices
136        //   index   n               -- artificial root r
137        //   indices n+1..n+1+k      -- gadget terminals t_v for v in V_p,
138        //                              listed in increasing order of v.
139        let prized: Vec<usize> = (0..n).filter(|&v| source_prizes[v] > 0).collect();
140        let k = prized.len();
141        let root = n;
142        let gadget_terminal = |gadget_pos: usize| -> usize { n + 1 + gadget_pos };
143
144        let target_num_vertices = n + 1 + k;
145        let mut target_edges: Vec<(usize, usize)> = Vec::with_capacity(m + n + 2 * k);
146        let mut target_edge_weights: Vec<i64> = Vec::with_capacity(m + n + 2 * k);
147        let mut target_to_source_edge: Vec<Option<usize>> = Vec::with_capacity(m + n + 2 * k);
148        let mut target_to_include_vertex: Vec<Option<usize>> = Vec::with_capacity(m + n + 2 * k);
149
150        // 1. Original edges keep their cost.
151        for (idx, &(u, v)) in source_edges.iter().enumerate() {
152            target_edges.push((u, v));
153            target_edge_weights.push(source_edge_costs[idx]);
154            target_to_source_edge.push(Some(idx));
155            target_to_include_vertex.push(None);
156        }
157
158        // 2. Root-attachment edge (r, v) of cost omega for every v in V.
159        for v in 0..n {
160            target_edges.push((v, root));
161            target_edge_weights.push(omega);
162            target_to_source_edge.push(None);
163            target_to_include_vertex.push(None);
164        }
165
166        // 3. A shared offset prevents gadget terminals from becoming cheap
167        // root attachments: every optimal gadget terminal must be a leaf.
168        for (gadget_pos, &v) in prized.iter().enumerate() {
169            let t_v = gadget_terminal(gadget_pos);
170            let include_cost =
171                omega.checked_add(1).ok_or_else(|| {
172                    crate::rules::ReductionError::integer_overflow::<
173                        Self,
174                        SteinerTree<SimpleGraph, i64>,
175                    >("forming the Steiner gadget inclusion cost")
176                })?;
177            let omit_cost = beta
178                .checked_mul(source_prizes[v])
179                .and_then(|penalty| penalty.checked_add(include_cost))
180                .ok_or_else(|| {
181                    crate::rules::ReductionError::integer_overflow::<
182                        Self,
183                        SteinerTree<SimpleGraph, i64>,
184                    >("forming the Steiner gadget omission cost")
185                })?;
186            // The include edge marks a selected prized vertex.
187            target_edges.push((v, t_v));
188            target_edge_weights.push(include_cost);
189            target_to_source_edge.push(None);
190            target_to_include_vertex.push(Some(v));
191            // The omit edge pays the additional omitted prize.
192            target_edges.push((root, t_v));
193            target_edge_weights.push(omit_cost);
194            target_to_source_edge.push(None);
195            target_to_include_vertex.push(None);
196        }
197
198        // 4. Terminal set: r plus every gadget terminal t_v.
199        let mut terminals: Vec<usize> = Vec::with_capacity(k + 1);
200        terminals.push(root);
201        for gadget_pos in 0..k {
202            terminals.push(gadget_terminal(gadget_pos));
203        }
204
205        let target_graph = SimpleGraph::new(target_num_vertices, target_edges);
206        let target =
207            SteinerTree::<SimpleGraph, i64>::new(target_graph, target_edge_weights, terminals);
208
209        Ok(ReductionPCSFToSteinerTree {
210            target,
211            num_source_vertices: n,
212            num_source_edges: m,
213            target_to_source_edge,
214            target_to_include_vertex,
215        })
216    }
217}
218
219#[cfg(feature = "example-db")]
220pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
221    use crate::example_db::specs::RuleExampleSpec;
222    use crate::export::SolutionPair;
223    use crate::solvers::BruteForce;
224
225    vec![RuleExampleSpec {
226        id: "prize_collecting_steiner_forest_to_steiner_tree",
227        build: || {
228            // Canonical instance with the omit-edge actually
229            // selected at the optimum: path 0 - 1 - 2 with c(0,1)=10,
230            // c(1,2)=10, prizes p = (5, 1, 5), beta = 1, omega = 1. The
231            // optimum drops vertex 1 (paying p(1) = 1) rather than paying a
232            // size-10 edge to reach it.
233            let source = PrizeCollectingSteinerForest::<SimpleGraph, i64>::new(
234                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
235                vec![5, 1, 5],
236                vec![10, 10],
237                1,
238                1,
239            )
240            .unwrap();
241            let reduction = <PrizeCollectingSteinerForest<SimpleGraph, i64> as ReduceTo<
242                SteinerTree<SimpleGraph, i64>,
243            >>::reduce_to(&source)
244            .expect("reduction should succeed");
245            let target = reduction.target_problem();
246            let target_config = BruteForce::new()
247                .solve(target)
248                .expect("canonical target evaluation must succeed")
249                .expect("canonical PCSF -> SteinerTree example must have an optimal target tree");
250            let source_config = reduction.extract_solution(&target_config).unwrap();
251            crate::example_db::specs::assemble_rule_example(
252                &source,
253                target,
254                vec![SolutionPair {
255                    source_config: serde_json::to_value(source_config)
256                        .expect("solution serialization must succeed"),
257                    target_config: serde_json::to_value(target_config)
258                        .expect("solution serialization must succeed"),
259                }],
260            )
261        },
262    }]
263}
264
265#[cfg(test)]
266#[path = "../unit_tests/rules/prizecollectingsteinerforest_steinertree.rs"]
267mod tests;
problemreductions/rules/prizecollectingsteinerforest_steinertree.rs

problemreductions/rules/
prizecollectingsteinerforest_steinertree.rs
