SOME COMPLEXITY RESULTS ABOUT THRESHOLD GRAPHS

The problem of determining whether a graph G contains a threshold subgraph containing at least h edges is shown to be NP-complete if h is part of the input as the problems of minimum threshold completion, weighted 2-threshold partition and weighted 2-threshold covering. We also prove that the k-cyclic scheduling problem is NP-complete for all fixed k, a result used to show that deciding whether a threshold r-hypergraph contains a Hamiltonian cycle is NP-complete.