On Halin subgraphs and supergraphs

In this paper, the authors present two complexity results. The first pertains to the problem of finding Halin subgraphs while the second is a supergraph version which asks if a given graph is a subgraph of any Halin graph. Both of these problems are shown to be hard which, in turn, provides somewhat damaging evidence relative to the veracity of heuristic approaches employing Halin graphs as approximations.