2015/04/30 by Sudeshna Kolay, Kolay, Sudeshna, Fahad Panolan +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.CC #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1504.08120
arxiv created 2015/04/30 · openalex publication_date 2015/04/30 · arxiv updated 2015/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For fixed integers r,ℓ ≥ 0, a graph G is called an \em (r,ℓ)-graph if the vertex set V(G) can be partitioned into r independent sets and ℓ cliques. This brings us to the following natural parameterized questions: \sc Vertex (r,ℓ)-Partization and \sc Edge (r,ℓ)-Partization. An input to these problems consist of a graph G and a positive integer k and the objective is to decide whether there exists a set S⊆ V(G) (S⊆ E(G)) such that the deletion of S from G results in an (r,ℓ)-graph. These problems generalize well studied problems such as \sc Odd Cycle Transversal, \sc Edge Odd Cycle Transversal, \sc Split Vertex Deletion and \sc Split Edge Deletion. We do not hope to get parameterized algorithms for either \sc Vertex (r,ℓ)-Partization or \sc Edge (r,ℓ)-Partization when either of r or ℓ is at least 3 as the recognition problem itself is NP-complete. This leaves the case of r,ℓ ∈ \1,2\. We almost complete the parameterized complexity dichotomy for these problems. Only the parameterized complexity of \sc Edge (2,2)-Partization remains open. We also give an approximation algorithm and a Turing kernelization for \sc Vertex (r,ℓ)-Partization. We use an interesting finite forbidden induced graph characterization, for a class of graphs known as (r,ℓ)-split graphs, properly containing the class of (r,ℓ)-graphs. This approach to obtain approximation algorithms could be of an independent interest.