**Reference**:- Erik D. Demaine and Mikhail Rudoy, “Tree-Residue Vertex-Breaking: a new tool for proving hardness”, in
*Proceedings of the 20th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)*, Malmö, Sweden, June 18–20, 2018, 32:1–32:14. **Abstract**:-
In this paper, we introduce a new problem called Tree-Residue Vertex-Breaking (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 “vertex-breaking” operations (replacing a degree-*k*breakable vertex by*k*degree-1 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 NP-complete when the given multigraph is restricted to be planar and to consist entirely of degree-*k*breakable vertices. To demonstrate the use of TRVB, we give a simple proof of the known result that Hamiltonicity in max-degree-3 square grid graphs is NP-hard.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

*k*-uniform 2-regular hypergraphs is NP-complete for any*k*≥ 4, even when the incidence graph of the hypergraph is planar. **Comments**:- The full version of this paper is available as arXiv:1706.07900.
**Availability**:- The paper is available in PDF (548k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.