The NP-completeness of Eulerian Recurrent Length for 4-regular Eulerian Graphs

摘要

Graph theory is applied in wide area of computer science, including artificial intelligence and operations research. Indeed, graphs are used as models for practical problems. Graph theory, therefore, has potentiality for being useful tools in actual world. In this paper, a computational problem in graph theory, called Eulerian recurrent length, is introduced. The problem asks, for an Eulerian graph and a positive integer, whether there exists an Eulerian circuit of the Eulerian graph such that the length of a shortest subcycle in the Eulerian circuit is greater than or equal to the positive integer. The maximum length of shortest subcycles in Eulerian circuits of an Eulerian graph is referred to as the Eulerian recurrent length of the Eulerian graph by the author. The NP-completeness of the Eulerian recurrent length problem is proved even if each instance is restricted to a pair of a 4-regular graph and any constant greater than 330.