Better approximations of non-Hamiltonian graphs (Q1382268)

The problem of recognizing the class of non-sub-2-factor graphs (NS2F) is established to be NP-complete. Another proof of an earlier result about NP-ompleteness for the class of non-1-tough graphs (N1T) is also given. Both classes may have applications in generating, in polynomial time, random non-Hamiltonian graphs. In this paper it is argued that the class NS2F is substantially larger than the class N1T (the difference is a \(\text{D}^P\)-complete set) and, thus, is more suitable for the task of random generation of instances of non-Hamiltonian graphs.