In this question I have suggested a generalization of the notion of a set of points in the Euclidean plane being in convex configuration to the set of vertices of symmetric weighted graphs via $k$-optimal tours.
A natural follow-up question is how to generalize planar convex hulls accordingly.
From the observation that the relative order of the points of the convex hull within the sequence of an arbitrary tour without crossing edges through the entire set of points is always the same (when w.l.o.g. traversed in positive orientation) and from the fact that simple polygons represent a set of tours that fulfill a certain optimality criterion comes the idea for the following generalization of planar convex hulls to the vertices of weighted symmetric graphs:
The k-hull of the vertices of a weighted symmetric graph is their maximal subset that is encountered in the same relative order on all k-optimal tours in the graph; the edges of the k-hull are those that remain, when shortcutting non-hull vertices on an arbitrary $k$-optimal tour.
Question:
how can the $k$-hulls (as defined above) be calculated, i.e. can it be avoided to enumerate and "intersect" all $k$-optimal tours through a graph's vertices?
Edit 2017-04-20
meanwhile I have a better understanding of $k$-optimality and, following a suggestion of Stefan Kohl, I report it here in the spirit of sharing knowledge, even if there isn't a 100% relation to the stated problem.
Efficiently finding optimal replacements for subsets of tour-edges:
the problem, that has to be solved here, is to report the optimal replacement for $k$ of a tour's edges The key observation were:
that a subset of $k$ edges of a tour defines a linear forest, whose number of connected components can be anything from $1$ to $k$ and, that the number of connected components of the complement, i.e., of the "unselected" edges of same tour, equals that of the selected edges
for finding the optimal replacement for $k$ of a tour's edges, the set of unselected edges trivially doesn't influence the relative order of the candidate replacement sets; therefore it is possible, to formally retract each connected component of the unselected edges (lets call those components the "plumes" of a tour) to a "plume-edge".
The optimal set of replacement-edges is then the one, that constitutes to the optimal tour through subgraph that is induced by the adjacent vertices and, after setting the weight of the plume-edges to $0$ and adding a sufficiently high value to the other edges, so that it is guaranteed, that the plume-edges are contained in the optimal tour.
Reducing the problem of finding the optimal set of replacement edges to a fixed-size tsp, provides an entire arsenal of algorithms from brute force over branch-and-bound to LP based solvers.
Generating all optimization instances for optimally replacing $k$ of a tour's edges:
- the key observation was, that the plume-edges are pairwise not adjacent and thus are adjacent $2h$ vertices, $1\le h\le\lfloor\frac{k}{2}\rfloor$.
Every optimization instance for $k$ tour edges can therefore be represented by $h$ plume-edges plus $k-2h$ non-adjacent vertices.
The only algorithmic challenge is to avoid generating an optimization instance multiple times, which in turn means to generate each set of plume-edges only once. That can however be guaranteed by creating those tuples in ascending order of the smaller of the adjacent vertices and then, proceeding backwards trough the list of generated first vertices, iterate from the an plume-edge's first vertex to the end of the vertex list, skipping vertices, that are already the second vertex of a plume-edge.
Generalizing intersection or crossing of two edges to $k$ edges:
- the key observation was, that two geometrically intersecting or crossing edges (i.e. the maximum matching of a K_4 subgraph) can't simultaneously appear in an optimal tour. That same "mutex" situation can be identified in the $k$-optimal sets of replacement edges: if a pair vertices $\lbrace u,v\rbrace$ can be found in two such optimal replacement sets, in which $\lbrace u,v\rbrace$ isn't adjacent to a plume-edge and, if $(u,v)$ is an edge in one set, but not in the other, then those two sets are also mutually exclusive and can be defined as "crossing".
Generalizing separators to $k$-separators
a $k$-separator is an edge, that can't be part of any $k$-optimal tour, i.e. when removing all mutually exclusive edges and the two adjacent vertices renders the graph disconnected.
That generalizes directly to $k$-optimality by removing all incompatible replacement sets and the vertices that define the candidate edge.
Generalizing geometric convex hulls to $k$-opt hulls
the striking property of planar geometric convex hulls is, that the order of points on the convex hull is preserved int the optimal tour. The defining properties can be described as follows: it can be constructed from the largest triangle via greedy expansion, that preserves the property, that all edges, except the hull edges, are separator edges. That construction also generalizes directly to $k$-optimality, because any permutation of the hull-vertices would create a tour with $k$-separators and could thus not be $k$-optimal.
