Graph Decomposition

Josep Dı́az, Marı́a Serna, Paul G. Spirakis, Jacobo ToránCambridge 1997 · DOI · OpenAlex

Abstract

For some graph problems, the fact of restricting the input to planar graphs simplifies the computational complexity of the problem. However, there are some NP-complete problems that remain NP-complete even when restricted to planar graphs, for instance the Maximum Independent Set problem (see [GJ79]). We have already mentioned in the introduction that to find a constant approximation to the problem of the Maximum Independent Set for a general graph with n vertices is as difficult as to find an approximation to the problem of finding a Maximum Clique, which means that unless P=NP, the Maximum Independent Set problem cannot be approximated within n1−ε [Has96].
BibTeX
@inproceedings{daz1997graph,
  author = {Josep Dı́az and Marı́a Serna and Paul G. Spirakis and Jacobo Torán},
  title = {{Graph Decomposition}},
  booktitle = {Cambridge},
  year = {1997},
  doi = {10.1017/cbo9780511666407.007},
}

Loading related content...

Figure