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.