Independence and Domination in Path Graphs of Trees - Niepel, Ľudovít; Černý, Anton (Computing and Informatics, 2012)
The problems of determining the maximum cardinality of an independent set of vertices and the minimum cardinality of a maximal independent set of vertices of a graph are known to be NP-complete. We provide efficient algorithms for finding these values for path graphs of trees.