Margot, F.2006-02-132006-02-132006-02-13199410.1016/0166-218X(94)90214-3https://infoscience.epfl.ch/handle/20.500.14299/222761WOS:A1994NJ99700018The 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-completetext::journal::journal article::research article