Vertex deletion on split graphs: beyond 4-hitting set (Q5918994): Difference between revisions

Problem(s): The authors study the vertex deletion approach to two graph transformation problems, viz., Split to Block and Split to Threshold. Overview: The vertex deletion approach for selected graph problems consists of finding a minimum cardinality of vertices whose deletion results in the resultant graph having a particular property. Vertex deletion has been studied for a number of problems such as planarity, bipartiteness, and so on. In the current paper, the authors are concerned with transforming split graphs to block graphs and threshold graphs via vertex deletion. Principal contributions: \begin{itemize} \item[(a)] Parameterized algorithms and kernel upper bounds for the Split to Block graph problem (decision version) and an exact exponential algorithm for the optimization version. \item[(b)] A 3-factor approximation for the optimization version along with lower bounds based on the Unique Games conjecture. \item[(c)] Similar results for the Split to Threshold graph problem, with APX-hardness proved for the optimization version. \end{itemize} Evaluation: The paper is extremely well written and the contributions are novel and interesting. Furthermore, the authors go to great lengths to inform the audience about simple results that are obtainable (via Hitting Set in this case) and how they can be improved by exploiting the specialized structure of split graphs. Section 2 in particular will be very useful to the casual reader, who may not be familiar with all the terms used in the paper. The main results flow from a number of pre-processing and reduction rules. The soundness of each rule is easily established. However, put together, these rules are powerful enough to obtain the desired bounds.