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?