Some complexity results about threshold graphs

Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Review text

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\).

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Some complexity results about threshold graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1327235)