Counting maximal independent sets in directed path graphs

• We study the problem of counting maximal independent sets in directed path graphs.
• We show that the problem is #P-complete for directed path graphs.
• We present that the problem admits a polynomial-time solution for rooted directed path graphs.

The problem of counting maximal independent sets is #P-complete for chordal graphs but solvable in polynomial time for its subclass of interval graphs. This work improves upon both of these results by showing that the problem remains #P-complete when restricted to directed path graphs but that a further restriction to rooted directed path graphs admits a polynomial time solution.