Some complexity results about threshold graphs
type: Item
instance of: scholarly article
title: Some complexity results about threshold graphs
zbMATH Open document ID: 0802.90109
DOI: 10.1016/0166-218X(94)90214-3
published in: Discrete Applied Mathematics
publication date: 1994-06-15T00:00:00Z
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\).
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 590208
zbMATH Keywords: threshold problems
zbMATH Keywords: threshold subgraph problem
zbMATH Keywords: threshold completion problem
zbMATH Keywords: \(k\)-cyclic scheduling
zbMATH Keywords: clique
zbMATH Keywords: NP-complete
author: François Margot
reviewed by: Hartmut Noltemeier
MaRDI profile type: Publication
cites work: Q4165164
cites work: Two-Processor Scheduling with Start-Times and Deadlines
cites work: Threshold Numbers and Threshold Completions
cites work: Hamiltonian threshold graphs
cites work: Sufficient Conditions for Graphs to Have Threshold Number 2
cites work: Cyclic scheduling of offweekends
cites work: Threshold hypergraphs
cites work: The Complexity of the Partial Order Dimension Problem
Wikidata QID: Q127372854
description: scientific article; zbMATH DE number 590208