Problem Detail: Consider Weighted Independent Set in a path graph, i.e., a graph where all the vertices are in a single path. Does this problem have practical applications? What are some? This problem is used in many CS courses as an intro to the dynamic programming paradigm, but I don’t see any mention about whether this is useful practically or whether it is only mentioned for didactic purposes.
Asked By : Manohar
Answered By : Pål GD
I don’t think that the weighted independent set problem in paths has many applications. However, as you point out yourself, it is a very good introduction to dynamic programming and to algorithmic graph theory; This is one of very many problems that are NP-complete on general graphs but become simpler (or indeed trivial) on restricted input instances. When you know, and understand, the algorithm for (weighted) independent set in paths, it is not too hard to generalize this to (weighted) independent set in trees and even to graphs of bounded pathwidth and treewidth. I think that this problem on paths (maybe even on trees, but here I’d love to be corrected) is purely educational. Indeed, I have hard times finding reasonable applications to Independent Set as well as Vertex Cover, Clique and Dominating Set.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41208 Ask a Question Download Related Notes/Documents
