Linear-time algorithms for eliminating claws in graphs |
| |
Authors: | Flavia Bonomo-Braberman Julliano R Nascimento Fabiano S Oliveira Uéverton S Souza Jayme L Szwarcfiter |
| |
Affiliation: | 1. FCEyN, DC./CONICET-UBA. ICC, Universidad de Buenos Aires, Viamonte 430, C1053 CABA, Buenos Aires, Argentina;2. INF, Universidade Federal de Goiás, Goiás, 74690-90 Brazil;3. IME, Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 20550-900 Brazil;4. IC, Universidade Federal Fluminense, Rio de Janeiro, 24210-346 Brazil |
| |
Abstract: | Since many -complete graph problems are polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given graph to a claw-free graph, considering vertex elimination a 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 -hard in general and recognizing claw-free graphs is still a challenge, where the current best deterministic algorithm for a graph G consists of performing executions of the best algorithm for matrix multiplication, we present linear-time algorithms for CFVD on weighted block graphs and weighted graphs with bounded treewidth. Furthermore, we show that this problem on forests can be solved in linear time by a simpler algorithm, and we determine the exact values for full k-ary trees. On the other hand, we show that CFVD is -hard even when the input graph is a split graph. We also show that the problem is hard to be approximated within any constant factor better than 2, assuming the unique games conjecture. |
| |
Keywords: | claw-free graph vertex deletion weighted vertex deletion |
|
|