Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

D. Bauer, Haitze J. Broersma, A. Morgana, E. Schmeichel

Abstract

A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and $\mathcal{P}$$_{2}$ is a cycle structure property of graphs that is also NP-hard. Such a theorem is the well-known Chv\'{a}tal-Erd\"{o}s Theorem, which states that every graph $G$ with $\alpha \leq \kappa $ is Hamiltonian. Here $\kappa $ is the vertex connectivity of $G$ and $\alpha $ is the cardinality of a largest set of independent vertices of $G$. In another paper Chv\'{a}tal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than $\kappa $ independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the well-known theorem of Jung for graphs on $16$ or more vertices..
Original languageUndefined
Place of PublicationEnschede
PublisherUniversiteit Twente
Number of pages15
ISBN (Print)0169-2690
StatePublished - 1999

Publication series

NameMemorandum / Faculty of Mathematical Sciences
PublisherDepartment of Applied Mathematics, University of Twente
No.1499
ISSN (Print)0169-2690

Fingerprint

Graph in graph theory
Theorem
Hamiltonian graph
Graph theory
NP-complete problem
Vertex connectivity
Hamilton cycle
Large set
Property A
Cardinality
Polynomial time
Imply
Cycle

Keywords

  • MSC-05C38
  • EWI-3319
  • IR-65687
  • METIS-141297
  • MSC-68R10

Cite this

Bauer, D., Broersma, H. J., Morgana, A., & Schmeichel, E. (1999). Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion. (Memorandum / Faculty of Mathematical Sciences; No. 1499). Enschede: Universiteit Twente.

Bauer, D.; Broersma, Haitze J.; Morgana, A.; Schmeichel, E. / Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion.

Enschede : Universiteit Twente, 1999. 15 p. (Memorandum / Faculty of Mathematical Sciences; No. 1499).

Research output: ProfessionalReport

@book{e587396bc3614c4291fd1d11d3a45c63,
title = "Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion",
abstract = "A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and $\mathcal{P}$$_{2}$ is a cycle structure property of graphs that is also NP-hard. Such a theorem is the well-known Chv\'{a}tal-Erd\{"}{o}s Theorem, which states that every graph $G$ with $\alpha \leq \kappa $ is Hamiltonian. Here $\kappa $ is the vertex connectivity of $G$ and $\alpha $ is the cardinality of a largest set of independent vertices of $G$. In another paper Chv\'{a}tal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than $\kappa $ independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the well-known theorem of Jung for graphs on $16$ or more vertices..",
keywords = "MSC-05C38, EWI-3319, IR-65687, METIS-141297, MSC-68R10",
author = "D. Bauer and Broersma, {Haitze J.} and A. Morgana and E. Schmeichel",
note = "Imported from MEMORANDA",
year = "1999",
isbn = "0169-2690",
series = "Memorandum / Faculty of Mathematical Sciences",
publisher = "Universiteit Twente",
number = "1499",

}

Bauer, D, Broersma, HJ, Morgana, A & Schmeichel, E 1999, Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion. Memorandum / Faculty of Mathematical Sciences, no. 1499, Universiteit Twente, Enschede.

Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion. / Bauer, D.; Broersma, Haitze J.; Morgana, A.; Schmeichel, E.

Enschede : Universiteit Twente, 1999. 15 p. (Memorandum / Faculty of Mathematical Sciences; No. 1499).

Research output: ProfessionalReport

TY - BOOK

T1 - Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

AU - Bauer,D.

AU - Broersma,Haitze J.

AU - Morgana,A.

AU - Schmeichel,E.

N1 - Imported from MEMORANDA

PY - 1999

Y1 - 1999

N2 - A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and $\mathcal{P}$$_{2}$ is a cycle structure property of graphs that is also NP-hard. Such a theorem is the well-known Chv\'{a}tal-Erd\"{o}s Theorem, which states that every graph $G$ with $\alpha \leq \kappa $ is Hamiltonian. Here $\kappa $ is the vertex connectivity of $G$ and $\alpha $ is the cardinality of a largest set of independent vertices of $G$. In another paper Chv\'{a}tal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than $\kappa $ independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the well-known theorem of Jung for graphs on $16$ or more vertices..

AB - A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and $\mathcal{P}$$_{2}$ is a cycle structure property of graphs that is also NP-hard. Such a theorem is the well-known Chv\'{a}tal-Erd\"{o}s Theorem, which states that every graph $G$ with $\alpha \leq \kappa $ is Hamiltonian. Here $\kappa $ is the vertex connectivity of $G$ and $\alpha $ is the cardinality of a largest set of independent vertices of $G$. In another paper Chv\'{a}tal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than $\kappa $ independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the well-known theorem of Jung for graphs on $16$ or more vertices..

KW - MSC-05C38

KW - EWI-3319

KW - IR-65687

KW - METIS-141297

KW - MSC-68R10

M3 - Report

SN - 0169-2690

T3 - Memorandum / Faculty of Mathematical Sciences

BT - Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

PB - Universiteit Twente

ER -

Bauer D, Broersma HJ, Morgana A, Schmeichel E. Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion. Enschede: Universiteit Twente, 1999. 15 p. (Memorandum / Faculty of Mathematical Sciences; 1499).