The k-Cycling Dinner problem, and its placement in the computational complexity zoo

Abstract

In this paper, I introduce a new family of scheduling and routing problems. These problems are called the k-cycling dinner problems. Given a graph, the problem is to find a set of tuples of nodes for which the distance between these nodes is minimized under the following three constraints. Each node is present in exactly k tuples. Each pair of tuples is not allowed to share more than one node, and each node should have the same position within the tuple in all the tuples in which that node in present. I provide a constraint satisfaction program which is able to solve these problem, however this solution is not sufficiently fast. After explaining the necessary terms on Np-Completeness, I provide an NP-Completeness reduction proof for the 2-Cycling Dinner problem, which proves that the 2-Cycling Dinner problem is in the complexity class NP-Complete. This suggests that finding a solution to this problem would be very hard to do in polynomial time. This paper also contains an attempt to provide an NP-Completeness reduction proof for the 3-CD problem. These proofs offer strong arguments for researchers trying to solve these problems, to utilize approximation algorithms.