2017/07/12 by Bergougnoux, Benjamin, Kanté, Mamadou Moustapha
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1707.03584
Given a clique-width k-expression of a graph G, we provide 2O(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 2O(k)⋅ n time algorithm for Feedback Vertex Set. The best running times for all the considered cases were either 2O(k⋅ log(k))⋅ nO(1) or worse.