Rank Based Approach on Graphs with Structured Neighborhood
Benjamin Bergougnoux, Mamadou Moustapha Kanté, Kanté, Mamadou, · HAL (Le Centre pour la Communication Scientifique Directe) · 2018
In this paper, we combine the rank-based approach and the neighbor equivalence to obtain efficient algorithms for several connectivity problems such as Connected Dominating Set}, Node Weighted Steiner Tree, Maximum Induced Tree and Feedback Vertex Set. For all these algorithms, we obtain $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k\cdot \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ time algorithms parameterized respectively by clique-width, $\mathbb{Q}$-rank-width, rank-width and maximum induced matching width, which simplify and unify the known algorithms for each of the parameters and match asymptotically also the best time complexity for Dominating Set.