2
$\begingroup$

Let $G(V,E)$ be a complete symmetric graph without self-loops or parallel edges; depending on the context the edges may however be interpreted as a pair of antiparallel arcs of equal weight.

A vertex disjoint cycle cover is the set of arcs $\lbrace \left(i,\delta^{-1}(i)\right)\rbrace\subseteq E$ where $i$ denotes the vertex with label $i$ and $\delta^{-1}(i)$ is the vertex with the label that is mapped to position $i$ by a derangement $\delta$ of the vertex labels.

Questions:

is it guaranteed that we will eventually encounter a Hamilton cycle if we repeatedly

  • calculate a vertex disjoint cycle cover $C$ without pairs of antiparallel arcs of $G$
  • delete from $G$ an edge $e$ that is randomly selected from $C$ among the edges such that $\,G\setminus e\,$ still contains a vertex disjoint cycle cover without pairs of antiparallel arcs.

In case we always do eventually encounter a Hamilton cycle:
what is known about the TSP heuristic of always deleting from $G$ the edge of the current lightest cycle cover the edges that meet the constraints of random selection and will yield the lightest vertex disjoint cycle cover in the next iteration?

Ruling out cycle covers with pairs of antiparallel arcs is essential because otherwise $K_4$ would be a counterexample: the arcs of perfect matching would be a cycle cover and after having deleted two edges one would be left with the edges of the third perfect matching.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What do you mean "encounter" a Hamilton cycle ? That the cycle cover $C$ must be Hamiltonian at one point ? And can you confirm that you are talking about "vertex cycle covers", it seems that edge and vertex covers are both sometimes called "covers". Then surely not, select one vertex $v$. If at each second step, you always delete an edge adjacent to $v$, then you can always find a cycle cover where e.g. $v$ is in a triangle $T$, and all vertices of $G-T$ are in one large cycle (because $G-T$ is complete), up to the point where $v$ has degree $1$, so there is no more cycle cover of $G$. $\endgroup$
    – Thomas Lesgourgues
    Commented Oct 12, 2021 at 23:17
  • $\begingroup$ By encounter I do indeed mean that one of the generated vertex (disjoint) cycle covers will be a Hamilton cycle; I had in mind a human being that checks the sequence of generated vertex covers. The terminology for the generated subgraphs is very diverse; have also seen "cycle packing"; or "disjoint cycle cover"; I used "vertex disjoint cycle cover" following Bodo Manthey's terminology. Your ounter-example made clear that further constraints must be imposed on the edge that is deleted from the current vertex cycle cover $\endgroup$
    – Manfred Weis
    Commented Oct 13, 2021 at 2:49
  • $\begingroup$ My intuition is that it might be very difficult (if possible at all) to impose a constraint on the deleted edge such that you always encounter a Hamilton cycle. Make me think about some kind of Maker-Breaker game, you play against an opponent, but you can restrict its choices. There might be some intuition to gather from these, but it's not directly related. $\endgroup$
    – Thomas Lesgourgues
    Commented Oct 13, 2021 at 4:05
  • $\begingroup$ @MaxAlekseyev which graph are you referring to; the question asks for starting with a complete graph, which to my knowledge is alsways Hamiltonian? Or do you refer to one of the intermediate graphs that are generated by successive deletion of edges from the original graph? $\endgroup$
    – Manfred Weis
    Commented Oct 13, 2021 at 14:02
  • $\begingroup$ I missed that $G$ in question is a complete graph. For a non-complete Hamiltonian graph, there exists a counterexample. $\endgroup$
    – Max Alekseyev
    Commented Oct 13, 2021 at 14:10

1 Answer 1

Reset to default
1
$\begingroup$

The answer is No.

It is convenient to think about $G$ as an undirected graph, since a vertex disjoint cycle cover without pairs of antiparallel arcs in the directed graph corresponds to a vertex-disjoint cycle cover in its undirected counterpart (this correspondence works in the reverse direction as well, up to a direction of each cycle in the cover).

Consider a subgraph $H$ of $G:=K_7$ formed by the union of $K_5$ and $K_3$ sharing exactly one vertex:

It has the following properties:

  • $H$ is not Hamiltonian
  • $H$ contains a vertex-disjoint cycle cover
  • for every edge $e\in E(G)\setminus E(H)$, in $H\cup\{e\}$ there exists a vertex-disjoint cycle cover that contains $e$ and that is not a Hamiltonian cycle.

Last two properties enable to remove edges from $G$ according to the described procedure such that the result will be $H$ and no Hamiltonian cycle will be encountered along the way. However, $H$ is not Hamiltonian, and thus Hamiltonian cycle will never be encountered here.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .