7
$\begingroup$

There are certain graph theoretic problems (especially optimization problems), whose solution-subgraph (i.e. the set of vertices and edges)), is invariant under certain modifications (especially modifications of edge weights) of which some examples are

  • the set of edges constituting to the shortest paths between a pair of vertices does not change if all edge weights are multiplied by a positive factor; it may however change, if a constant value is added to each edge-weight.

  • the set of edges constituting to a minimum spanning tree doesn't change after multiplying the weights with a positive factor and/or adding a constant value; it may however change, if the transformation is only applied to the weights of edges that are adjacent to some given vertex (e.g. after adding "node weights")

  • the set of edges constituting to either the shortest Hamilton cycle as well as the one constituting to the minimum weight maximal matching, are invariant to changes of "node weights"

the last example is special in that an NP-hard problem and an efficiently solvable problem are apparently invariant under the same kind of edge-weight modifications.

I would like to know, if those kinds of invariants have already been investigated in the spirit of an "Erlangen Program".

$$ $$ Addendum

David's example of a shortest-path preserving transformation makes clear, that the algorithm that is used to calculate the shortest path may also play a role in the definition of invariance.

There seem to be "strongly" invariant transformations that preserve the solution subgraph under every algorithm that determines that same subgraph in the unmodified graph and, also "weekly" invariant transformations that depend on the underlying algorithm.

That observation may also indicate, that a classification of algorithms based on the solution-set preserving transformations they support is also an interesting aspect of characterising the invariants of graph transformations.

$\endgroup$
  • 3
    $\begingroup$ Incidentally, a more useful shortest-path-preserving transformation (in directed graphs) is to assign (arbitrarily) a real-valued potential to each vertex of the graph, and adjust each edge weight by subtracting the potential of its source vertex and adding the potential of its destination vertex. This transformation is what is behind both Johnson's algorithm and A*. $\endgroup$ – David Eppstein Dec 30 '15 at 7:31
  • 3
    $\begingroup$ As for transformations on minimum spanning trees: they're invariant under any monotonic edge-weight transformation that is applied globally. $\endgroup$ – David Eppstein Dec 30 '15 at 7:31
  • $\begingroup$ @DavidEppstein your examples nicely demonstrate the current situation: the transformations are beneficially utilized, but are themselves not in the focus of interest (my perception) but rather play the role of tools. I bet that not very many people (including me) were aware of your examples of transformations. $\endgroup$ – Manfred Weis Dec 30 '15 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.