Fast exact algorithms for some connectivity problems parameterized by clique-width

Given a clique-width k-expression of a graph G, we provide 2 O ( k ) ⋅ n time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree, Connected Dominating Set, or Connected Vertex Cover. We also propose a 2 O ( k ) ⋅ n time algorithm for Feedback Vertex Set. The best running times for all the considered problems were 2 O ( k ⋅ log ⁡ ( k ) ) ⋅ n O ( 1 ).

Authors

• Benjamin Bergougnoux
• Mamadou Kanté

Keywords

• Clique-width
• Module-width
• Single exponential algorithm
• Feedback vertex set
• Connected σ, ρ -domination