congresos y reuniones científicas
Linear-time Algorithms for Eliminating Claws in Graphs
BONOMO, FLAVIA; NASCIMENTO, JULLIANO; OLIVEIRA, FABIANO; SOUZA, UÉVERTON; SZWARCFITER, JAYME
Conferencia; The 26th International Computing and Combinatorics Conference (COCOON); 2020
Since many NP-complete graph problems have been shown polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining thedistance of a given graph to a claw-free graph, considering vertex elimination as measure.Claw-free Vertex Deletion (CFVD) consists of determining the minimum number of vertices to be removed from a graph such that the resulting graph is claw-free.Although CFVD is NP-complete in general and recognizing claw-free graphs is still a challenge, where the current best algorithm for a graph G has the same running time of the best algorithm for matrix multiplication, we present linear-time algorithms for CFVD on weighted block graphs and weighted graphs withbounded treewidth. Furthermore, we show that this problem can be solved in linear time by a simpler algorithm on forests, and we determine the exact values for full k-ary trees.On the other hand, we show that Claw-free Vertex Deletion is NP-complete even when the input graph is a split graph. We also show that the problem is hard to approximate within any constant factor better than 2, assuming the Unique GamesConjecture.