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-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
