Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952423 | Theoretical Computer Science | 2016 | 10 Pages |
Abstract
The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G, a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, F, of graphs. In general the family F is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define F, we take algebraic route. More formally, given a fixed positive integer r, we define Fr as the family of graphs where for each GâFr, the rank of the adjacency matrix of G is at most r. Using the family Fr we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: r-Rank Vertex Deletion, r-Rank Edge Deletion and r-Rank Editing. These problems generalize the classical Vertex Cover problem and a variant of the d-Cluster Editing problem. We first show that all the three problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2O(klogâ¡r)nO(1) for r-Rank Vertex Deletion, and an algorithm for r-Rank Edge Deletion and r-Rank Editing running in time 2O(f(r)klogâ¡k)nO(1). We complement our FPT result by designing polynomial kernels for these problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
S.M. Meesum, Pranabendu Misra, Saket Saurabh,