Vertex Weights are a means to modify the weight of an edge by adding to it the weights of its adjacent vertices. The motivation for adding vertex weights to edge weights is two-fold: the relative order of regular spanners when sorted according to sum of (modified) edge weights is invariant under the addition of vertex weights and they give control over the topology of non-regular spanners whose sum of (modified) edge weights provides bounds on value of the optimal regular spanner.

The Held-Karp lower bound for the Traveling Salesman Problem is a prominent example for the successful application of vertex weights, where objective is to determine a set of vertex weights that yields the so-called 1-tree with maximal sum of unmodified edge-lengths.
The optimal values of the vertex weights are determined iteratively by increasing the weight of vertices whose degree in the calculated Minimum Spanning Tree is greater than two.


can the set of vertex weights that yields the highest lower bound for k-regular spanners with minimal sum of edge weights be determined directly, i.e. without iterative improvement?

The reason for asking is that I supect, that the calculation of the initial vertex weights is subjected to constraints derived from the weight of individual edges and maybe also non-negativity constraints, e.g., letting $\pi_i$ denote the weight of vertex $v_i$ and \omega_{ij} the weight of edge $e_{ij}$,

$\max \sum_i\pi_i$
$0\le\pi_i\quad\forall i$
$\pi_i+\pi_j\le\omega_{ij}\quad\forall \lbrace{i,j\rbrace} $

and the essence of my question is whether constraints based on $k$-tuples of adjacent edges and maybe dropping the non-negativity constraints would leverage. the potential of vertex weights.

Example $k=2$:
Hamilton cycles are special (i.e. connected) two-regular spanners and consequently it seems more appropriate to determine the vertex weights $\pi_i$ via the weight-sum of pairs of edges that are adjacent to $v_i$, i.e.

$\pi_h+2\pi_i+\pi_j\ \le\ \omega_{hi}+\omega_{ij}\quad\forall\lbrace h,i,j\rbrace$

and analogous for $k\gt 2$

In the $k=2$ case it is also tempting to suspect that the set of edges $e_{ij}$ that satisfy $\omega_{ij}-\pi_i-\pi_j\ \lt 0$ constitiute to the minimum weight perfect matching for graphs with an even number of vertices.
It is further tempting that the resulting vertex weights yield the graph, that is critically free of negative cycles.


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.