Unsolved Algorithmic Problems on Trees
Stephen T. Hedetniemi, T.W. Haynes · AKCE International Journal of Graphs and Combinatorics · 2006
The literature on algorithms and complexity results for domination and domination-related problems is extensive, and deals with a somewhat bewildering variety of concepts and definitions. At the same time, what one observes is that no matter what the definition or concept is, an algorithm problem related to that concept is almost always solvable in linear time when the inputs are restricted to trees. The fact that this is so follows almost directly from the now well-developed theory of algorithms on partial k -trees, or graphs of bounded treewidth. In light of this, it is somewhat surprising that quite a few algorithmic problems on trees remain unsolved. In this paper we offer a list of more than 60 algorithm problems that have yet to be solved for trees, quite a few of which are newly defined here. For about 50 of these problems the associated NP-completeness questions have not yet been settled either.