To be or not to be Yutsis: Algorithms for the decision problem

Moreover, we give the numbers of Yutsis and non-Yutsis cubic graphs with up to 30 vertices and cubic polyhedra with up to 40 vertices. All these numbers have been computed by two independent programs in order to reduce the probability of error. Since the decision problem whether a given cubic graph is Yutsis or not is NP-complete, we could not hope for a polynomial time worst case performance of our programs. Nevertheless the programs described in this article are very fast on average.