<p>A <strong>master solution</strong> for an instance of a combinatorial problem is a solution with the property that it is optimal for any sub instance.<br>
<span class="math-container">$~$</span>  </p>

<blockquote>
  <p>Martijn van Ee, René Sitters:<br>
  On the Complexity of Master Problems.<br>
  Proceedings of MFCS-2015, LNCS 9235, pp 567-576<br>
  <a href="https://link.springer.com/chapter/10.1007%2F978-3-662-48054-0_47" rel="nofollow noreferrer">https://link.springer.com/chapter/10.1007%2F978-3-662-48054-0_47</a> </p>
</blockquote>

<p><span class="math-container">$~$</span>  </p>

<blockquote>
  <p>Deineko, V.G., Rudolf, R., Woeginger, G.J.:<br>
  Sometimes travelling is easy: The master tour problem.<br>
  SIAM Journal on Discrete Mathematics 11, 1998, pp 81–93.<br>
  <a href="https://epubs.siam.org/doi/10.1137/S0895480195281878" rel="nofollow noreferrer">https://epubs.siam.org/doi/10.1137/S0895480195281878</a></p>
</blockquote>

CC BY-SA 4.0
2018-10-23T22:42:12.450Z
Thanks for the answer! I do not in fact need something quite as strong as this however. I only need the property that any optimal solution in the original graph is a solution in the subgraph (it doesn't necessarily need to be the optimal solution in the subgraph). If there is a *different* term for this property, great. Otherwise, I'll checkmark this answer in a few days.
user1246462
CC BY-SA 4.0
2018-10-23T08:18:04.563Z
2018-10-23T08:18:04.563Z
Gamow
<p>Suppose one is given a graph optimization problem where the optimal solution <span class="math-container">$S$</span> for the problem on graph <span class="math-container">$G$</span> can be used as a solution for any subgraph of <span class="math-container">$G$</span>. In other words, given <span class="math-container">$S$</span> is an optimal solution for the problem on <span class="math-container">$G$</span>, then <span class="math-container">$S \wedge G_i$</span> is a solution on <span class="math-container">$G_i$</span> all <span class="math-container">$G_i \subseteq G$</span>. Is there a canonical name for this property for a graph optimization problem? </p>

<graph-theory><graph-algorithms><optimization>
Problem property name where an optimal solution in a graph can be used as a solution in any subgraph
user1246462
# Problem property name where an optimal solution in a graph can be used as a solution in any subgraph

(Asked by: username_0 on 2018-10-23)

Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal solution for the problem on $G$, then $S \wedge G\_i$ is a solution on $G\_i$ all $G\_i \subseteq G$. Is there a canonical name for this property for a graph optimization problem?

**Tags:** graph-theory, graph-algorithms, optimization

---

## 1 answers

### Answer by username_1 on 2018-10-23. Score: 1 | Accepted answer

A **master solution** for an instance of a combinatorial problem is a solution with the property that it is optimal for any sub instance.  
$~$

> Martijn van Ee, René Sitters:  
> On the Complexity of Master Problems.  
> Proceedings of MFCS-2015, LNCS 9235, pp 567-576  
> <https://link.springer.com/chapter/10.1007%2F978-3-662-48054-0_47>

$~$

> Deineko, V.G., Rudolf, R., Woeginger, G.J.:  
> Sometimes travelling is easy: The master tour problem.  
> SIAM Journal on Discrete Mathematics 11, 1998, pp 81–93.  
> <https://epubs.siam.org/doi/10.1137/S0895480195281878>

> **Comments:**
> **username_0**: Thanks for the answer! I do not in fact need something quite as strong as this however. I only need the property that any optimal solution in the original graph is a solution in the subgraph (it doesn't necessarily need to be the optimal solution in the subgraph). If there is a *different* term for this property, great. Otherwise, I'll checkmark this answer in a few days.  

---

