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.
maximal independent sets directed path graphs algorithms counting problem