Algorithms for deletion problems on split graphs

2019/06/24 by Dekel Tsur, Tsur, Dekel
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1906.10012

arxiv created 2019/07/25 · arxiv updated 2019/07/26

Abstract

In the Split to Block Vertex Deletion and Split to Threshold Vertex Deletion problems the input is a split graph G and an integer k, and the goal is to decide whether there is a set S of at most k vertices such that G-S is a block graph and G-S is a threshold graph, respectively. In this paper we give algorithms for these problems whose running times are O^*(2.076^k) and O^*(2.733^k), respectively.

Related

• On fixed-parameter algorithms for Split Vertex Deletion
• A simple (2+ε)-approximation algorithm for Split Vertex Deletion
• A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion
• Parameterized vertex deletion problems for hereditary graph classes with\n a block property
• Faster parameterized algorithm for Cluster Vertex Deletion