[Rule] PrizeCollectingSteinerForest to SteinerTree

[zhangjieqingithub]

Source

PrizeCollectingSteinerForest

Target

SteinerTree

Motivation

This is the natural companion rule for the biology-paper PCSF model.

The key modeling point is:

• the artificial root belongs in the reduction rule,
• not in the base PCSF model.

This rule records the paper's standard idea: turn a forest into a single tree in an augmented graph by adding an artificial root, while compiling the omitted-prize tradeoff into the target tree formulation through auxiliary prize gadgets.

Reference

• Nurcan Tuncbag et al., "Simultaneous Reconstruction of Multiple Signaling Pathways via the Prize-Collecting Steiner Forest Problem," Journal of Computational Biology 20(2):124-136, 2013. https://doi.org/10.1089/cmb.2012.0092
• Nurcan Tuncbag et al., "Simultaneous Reconstruction of Multiple Signaling Pathways via the Prize-Collecting Steiner Forest Problem," RECOMB 2012, LNBI 7262, pp. 287-301, 2012. https://doi.org/10.1007/978-3-642-29627-7_31

The paper gives the exact PCSF objective
f'(F) = beta * sum_{v notin V_F} p(v) + sum_{e in E_F} c(e) + omega * kappa(F)
and explains the artificial-root transformation by attaching a new root to every original vertex with cost omega.

Reduction Algorithm

This proposal is for the first concrete undirected repo variant.

Let the source instance be:

• a graph G = (V, E)
• vertex prizes p(v) >= 0
• edge costs c(e) >= 0
• parameters beta >= 0, omega >= 0

Construct an augmented graph H as follows.

1. Add a new artificial root r.

2. Keep every original edge e in E with its original cost c(e).

3. For each original vertex v in V, add a root-attachment edge (r,v) of cost omega.

4. For each original vertex v, add a constant-size prize gadget that compiles the omitted-prize term beta * p(v) into ordinary Steiner-tree edge costs.
   The gadget should satisfy:

   • if v is included in the projected forest, the gadget can be connected with no omitted-prize charge for v,
   • if v is omitted from the projected forest, the gadget contributes exactly beta * p(v) in the target tree objective.

5. Declare the root and the prize-gadget terminals as the target terminal set.

6. Solve the resulting SteinerTree instance on H.

7. Recover the source forest by deleting:

   • the artificial root r,
   • the root-attachment edges,
   • the auxiliary prize-gadget edges and vertices.

The remaining projected subgraph on the original vertex set is the recovered forest F.

Correctness intuition

• Every tree component of a source forest becomes attached exactly once to the artificial root, so the target tree pays one copy of omega per forest component.
• Original selected edges keep their original costs.
• The prize gadget at each vertex ensures that omitted vertices contribute exactly beta * p(v), while included vertices do not.
• After removing the root and auxiliary gadget structure, the target tree projects back to a forest on the original graph.
• Conversely, any source forest can be lifted to one connected tree in the augmented graph by attaching each component once to r and satisfying each omitted-vertex gadget locally.

Therefore the target tree objective matches the source PCSF objective, up to at most a fixed additive constant introduced by the chosen prize-gadget normalization.

Size Overhead

Let:

• n = num_vertices
• m = num_edges

For any standard constant-size per-vertex prize gadget, the augmented instance has linear overhead.

A simple one-gadget-per-vertex encoding gives the conservative bounds:

Target metric	Formula
num_vertices	<= 2 * n + 1
num_edges	<= m + 3 * n
num_terminals	<= n + 1

The exact constants depend on the concrete prize gadget fixed during implementation, but the overhead is linear in the source graph size.

Validation Method

• Compare the target Steiner-tree optimum against brute-force PCSF evaluation on small graphs.
• Check projection:
  • remove the root and all auxiliary gadget structure,
  • verify that the remaining original subgraph is a forest.
• Check objective preservation on hand-solvable examples:
  • original-edge costs must match exactly,
  • the number of root attachments must equal the number of forest components,
  • omitted vertices must contribute exactly beta * p(v) through the gadget.
• Include cases with:
  • singleton components,
  • empty forest optimum,
  • one connected tree optimum,
  • multiple-tree optimum caused by a large omega / edge-cost tradeoff.

Example

Take the source instance from the model issue:

• path 0 - 1 - 2
• edge costs c(0,1) = 1, c(1,2) = 6
• vertex prizes p(0) = 5, p(1) = 2, p(2) = 5
• beta = 1
• omega = 2

The optimal source forest is:

• edge set {(0,1)}
• with vertex 2 kept as a singleton component

Its source objective is:

• edge cost 1
• omitted prize 0
• component penalty 2 * 2 = 4

Total:
5

In the augmented target instance:

• add root r,
• add root-attachment edges (r,0), (r,1), (r,2), each of cost 2,
• add one prize gadget per vertex.

A lifted target tree corresponding to the optimal source forest:

• uses the original edge (0,1),
• uses one root attachment for the component {0,1},
• uses one root attachment for the singleton component {2},
• satisfies all three vertex gadgets in their "included" mode.

So the target objective is:

• original edge contribution 1
• two root attachments contributing 4
• zero omitted-prize gadget charge

Total:
5

After deleting the root and auxiliary gadget structure, the target tree projects back to the source forest with components {0,1} and {2}.

BibTeX

@article{TuncbagEtAl2013PCSF,
  author  = {Nurcan Tuncbag and Alfredo Braunstein and Andrea Pagnani and Shao-Shan Carol Huang and Jennifer Chayes and Christian Borgs and Riccardo Zecchina and Ernest Fraenkel},
  title   = {Simultaneous Reconstruction of Multiple Signaling Pathways via the Prize-Collecting Steiner Forest Problem},
  journal = {Journal of Computational Biology},
  volume  = {20},
  number  = {2},
  pages   = {124--136},
  year    = {2013},
  doi     = {10.1089/cmb.2012.0092},
  url     = {https://doi.org/10.1089/cmb.2012.0092}
}

@inproceedings{TuncbagEtAl2012RECOMB,
  author    = {Nurcan Tuncbag and Alfredo Braunstein and Andrea Pagnani and Shao-Shan Carol Huang and Jennifer Chayes and Christian Borgs and Riccardo Zecchina and Ernest Fraenkel},
  title     = {Simultaneous Reconstruction of Multiple Signaling Pathways via the Prize-Collecting Steiner Forest Problem},
  booktitle = {Research in Computational Molecular Biology (RECOMB 2012)},
  series    = {Lecture Notes in Bioinformatics},
  volume    = {7262},
  pages     = {287--301},
  year      = {2012},
  publisher = {Springer},
  doi       = {10.1007/978-3-642-29627-7_31},
  url       = {https://doi.org/10.1007/978-3-642-29627-7_31}
}