Deleting to Structured Trees

Deleting to Structured Trees

Research

InterestsPublicationsTalksWorkshops and SchoolsPhD ThesisMasters Thesis

Deleting to Structured Trees

This talk was based on joint work with Pratyush Dayal and was delivered (remotely) at COCOON 2019. Here, we consider a natural variant of the well-known Feedback Vertex Set problem, namely the problem of deleting a small subset of vertices or edges to a full binary tree. This version of the problem is motivated by real-world scenarios that are best modeled by full binary trees. We establish that both versions of the problem are NP-hard, which stands in contrast to the fact that deleting edges to obtain a forest or a tree is equivalent to the problem of finding a minimum cost spanning tree, which can be solved in polynomial time. We also establish that both problems are FPT by the standard parameter.