1
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

This amounts to an application: Suppose there are service areas on a certain long highway, every 20 miles. A company wants to open up restaurants at some of these sites. It estimates a potential revenue from each site. The company would not want to open up restaurants that are within 30 miles of each other (to avoid self-competition).

This can be modeled as node weighted path graphs where each site is a node, weight is the estimated revenue from the site and two successive sites make edges between them. A max node weighted independent set in this graph is the revenue maximizing non competing sites.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.