Some complexity results about threshold graphs (Q1327235)

The author is concerned with the complexity of a family of threshold problems, e.g. the threshold subgraph problem (given a graph \(G= (V,E)\) and a positive integer \(h\) as input; decide whether there is a subgraph \(T= (V,E')\) with \(| E'|\geq h\) such that \(T\) is a threshold graph), the threshold completion problem (given a graph \(G= (V,E)\) and a positive integer \(h\) as input; decide whether there is a threshold graph \(G'= (V,E')\) which can be obtained by adding at most \(h\) edges), \(k\)- cyclic scheduling (given a finite set \(C\) and positive integers \(I(c)\) for each \(c\in C\) and integer bound \(B\); is there a cyclic ordering of \(C\), such that the sum of the values of any \(k\) consecutive elements is at most \(B\)) among others. By the partition of threshold graphs into a clique \(K\) and an order independent set \(I\) the author can show that Clique and Threshold Subgraph are polynomially transformable problems. This shows that Threshold Subgraph is NP-complete as well as the threshold completion problem. By some other polynomial transformations it is shown that \(k\)- cyclic scheduling is NP-complete too for \(k\geq 3\).