Abstract
In this paper, we introduce a new problem called TreeResidue VertexBreaking (TRVB): given a multigraph G some of whose vertices are marked "breakable," is it possible to convert G into a tree via a sequence of "vertexbreaking" operations (replacing a degreek breakable vertex by k degree1 vertices, disconnecting the k incident edges)?
We characterize the computational complexity of TRVB with any combination of the following additional constraints: G must be planar, G must be a simple graph, the degree of every breakable vertex must belong to an allowed list B, and the degree of every unbreakable vertex must belong to an allowed list U. The two results which we expect to be most generally applicable are that (1) TRVB is polynomially solvable when breakable vertices are restricted to have degree at most 3; and (2) for any k >= 4, TRVB is NPcomplete when the given multigraph is restricted to be planar and to consist entirely of degreek breakable vertices. To demonstrate the use of TRVB, we give a simple proof of the known result that Hamiltonicity in maxdegree3 square grid graphs is NPhard.
We also demonstrate a connection between TRVB and the Hypergraph Spanning Tree problem. This connection allows us to show that the Hypergraph Spanning Tree problem in kuniform 2regular hypergraphs is NPcomplete for any k >= 4, even when the incidence graph of the hypergraph is planar.
BibTeX  Entry
@InProceedings{demaine_et_al:LIPIcs:2018:8858,
author = {Erik D. Demaine and Mikhail Rudoy},
title = {{TreeResidue VertexBreaking: a new tool for proving hardness}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {32:132:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8858},
URN = {urn:nbn:de:0030drops88586},
doi = {10.4230/LIPIcs.SWAT.2018.32},
annote = {Keywords: NPhardness, graphs, Hamiltonicity, hypergraph spanning tree}
}
Keywords: 

NPhardness, graphs, Hamiltonicity, hypergraph spanning tree 
Collection: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 