We continue the study of boundary classes for NP-hard problems and focus on seven NP-hard graph problems involving non-local properties: HAMILTONIAN CYCLE, HAMILTONIAN CYCLE THROUGH SPECIFIED EDGE, HAMILTONIAN PATH, FEEDBACK VERTEX SET, CONNECTED VERTEX COVER, CONNECTED DOMINATING SET and GRAPH VCCON DIMENSION. Our main result is the determination of the first boundary class for FEEDBACK VERTEX SET. We also determine boundary classes for HAMILTONIAN CYCLE THROUGH SPECIFIED EDGE and HAMILTONIAN PATH and give some insights on the structure of some boundary classes for the remaining problems.

Boundary classes for graph problems involving non-local properties / Munaro, Andrea. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 692:(2017), pp. 46-71. [10.1016/j.tcs.2017.06.012]

Boundary classes for graph problems involving non-local properties

Andrea Munaro
2017

Abstract

We continue the study of boundary classes for NP-hard problems and focus on seven NP-hard graph problems involving non-local properties: HAMILTONIAN CYCLE, HAMILTONIAN CYCLE THROUGH SPECIFIED EDGE, HAMILTONIAN PATH, FEEDBACK VERTEX SET, CONNECTED VERTEX COVER, CONNECTED DOMINATING SET and GRAPH VCCON DIMENSION. Our main result is the determination of the first boundary class for FEEDBACK VERTEX SET. We also determine boundary classes for HAMILTONIAN CYCLE THROUGH SPECIFIED EDGE and HAMILTONIAN PATH and give some insights on the structure of some boundary classes for the remaining problems.
Boundary classes for graph problems involving non-local properties / Munaro, Andrea. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 692:(2017), pp. 46-71. [10.1016/j.tcs.2017.06.012]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2930719
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact