1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user1246462 Oct 23 '18 at 22:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.