Paper “Finding Optimal Solutions With Neighborly Help”Springer Nature In this paper, we focus on two prototypical graph problems, Colorability and Vertex Cover. For example, we show that it is NPhard to compute an optimal coloring for a graph from optimal colorings for all its onevertexdeleted subgraphs, and that this remains true even when optimal solutions for all oneedgedeleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) oneedgeadded supergraphs is in P. We observe that Vertex Cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Further Reading
