On the equitable Hamiltonian Cycle problem

Abstract: Kinable, Smeulders, Delcour, and Spieksma (2017) introduced the Equitable TSP (E-TSP). In the E-TSP, we are given an even number of cities and distances between each pair of these. Instead of finding a tour of minimum length, Kinable et al. (uniquely) decomposed the tour in two perfect matchings, one with “even” edges and one with “odd” edges and the goal is to minimize the difference between the costs of the two perfect matchings. Kinable et al. show that the E-TSP is strongly NP-hard by reduction from Hamiltonian Cycle. The reduction resembles the reduction to show that TSP is strongly NP-hard. In the reduction for TSP, it suffices to set each distance to one of two values, e.g., 0 or 1. The reduction used for the E-TSP, however, needs to have many different values for the distances. This raises the question whether the optimal solution-value to the E-TSP when each distance can only be one of two values needs to be 0 or is positive.

We generalized this question to the Equitable Hamiltionian Cycle Problem: given a complete graph on an even number of vertices in which each edge is either red or blue, can we find a tour on all vertices such that the “even” perfect matching has as many red edges as the “odd” perfect matching. We will show that the answer to this question is NO and YES, and for the YES-case we present the idea on how to find such a tour in O(n log n) or even O(n) time. Furthermore, if time permits, we also discuss how well some simple local search algorithm will perform.

This is joint work with Frits Spieksma and Tim Ophelders (TU Eindhoven)

Date: May 16, 2018 at 14:30 h
Venue: Republica 701, Sala 33.
Speaker: Tjark Vredeveld
Affiliation: Maastricht University
Coordinator: Prof. José Verschae
More info at:
Event website

Posted on May 14, 2018 in AGCO, Seminars