An edge-bicolored graph G=(V,R∪B) is called Red/Blue-split graph if there exists a partition IB and IR of V such that IB and IR are independent sets in (V,B) and (V,R), respectively. Red/Blue-split graphs generalize several well studied graph classes including split graphs, bipartite graphs and König–Egerváry graphs. In this paper we consider the algorithmic complexity of various optimization problems like minimum edge (or vertex) deletion and maximum edge (or vertex) induced subgraph related to Red/Blue split graphs. All these problems are NP-hard and thus we look at them from algorithmic paradigms that are meant for coping with NP-hardness. We obtain various hardness as well as algorithmic results for these problems in the realm of approximation algorithms and parameterized complexity. The main tool we use to obtain all our results is polynomial time transformations between appropriate problems. On the way, we also resolve some problems related to inapproximability about certain optimization problems mentioned by Korach et al. (2006) [17]. © 2017 Elsevier B.V.

Sounaka Mishra

Department of Mathematics

Aluminum alloys

Approximation algorithms

Computational complexity

Graphic methods

Hardness

Optimization

Parallel processing systems

Polynomial approximation

Polynomials

Algorithmic complexity

Bipartite graphs

INAPPROXIMABILITY

Induced subgraphs

Optimization problems

PARAMETERIZED COMPLEXITY

PARAMETRIZED COMPLEXITY

RED/BLUE-SPLIT GRAPHS

Graph theory

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Theoretical Computer Science

We investigate the parameterized complexity of VERTEX COVER parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an O∗(2.618k) algorithm for the problem. Here, k is the excess of the vertex cover size over the LP optimum, and we write O∗ (f(k)) for a time complexity of the form O(f(k)nO(1)). We proceed to show that a more sophisticated branching algorithm achieves a running time of O∗(2.3146k). Following this, using previously known as well as new reductions, we give O∗(2.3146k) algorithms for the parameterized versions of ABOVE GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION, and ALMOST 2-SAT, and O∗(1.5214k) algorithms for KÖNIG VERTEX DELETION and VERTEX COVER parameterized by the size of the smallest odd cycle transversal and König vertex deletion set. These algorithms significantly improve the best known bounds for these problems. The most notable improvement among these is the new bound for ODD CYCLE TRANSVERSAL - this is the first algorithm that improves on the dependence on k of the seminal O∗(3k) algorithm of Reed, Smith, and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of VERTEX COVER with at most 2k - c log k vertices. Our kernel is simpler than previously known kernels achieving the same size bound. © 2014 ACM.

Fulltext

ACM Transactions on Algorithms

Faster parameterized algorithms using linear programming

A graph is König-Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been studied extensively from a graph-theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding König-Egerváry subgraphs of a given graph. In particular, given a graph G and a nonnegative integer k, we are interested in the following questions: 1. does there exist a set of k vertices (edges) whose deletion makes the graph König- Egerváry? 2. does there exist a set of k vertices (edges) that induce a König-Egerváry subgraph? We show that these problems are NP-complete and study their complexity from the points of view of approximation and parameterized complexity. Towards this end, we first study the algorithmic complexity of Above Guarantee Vertex Cover, where one is interested in minimizing the additional number of vertices needed beyond the maximum matching size for the vertex cover. Further, while studying the parameterized complexity of the problem of deleting k vertices to obtain a König-Egerváry graph, we show a number of interesting structural results on matchings and vertex covers which could be useful in other contexts. © 2010 Springer Science+Business Media, LLC.

Algorithmica (New York)

The complexity of König subgraph problems and above-guarantee vertex cover

A graph is König-Egerváry if the size of a minimum vertex cover equals the size of a maximum matching in the graph. We show that the problem of deleting at most k vertices to make a given graph König-Egerváry is fixed-parameter tractable with respect to k. This is proved using interesting structural theorems on matchings and vertex covers which could be useful in other contexts. We also show an interesting parameter-preserving reduction from the vertex-deletion version of red/blue-split graphs [4,9] to a version of Vertex Cover and as a by-product obtain 1 the best-known exact algorithm for the optimization version of Odd Cycle Transversal [15]; 1 fixed-parameter algorithms for several vertex-deletion problems including the following: deleting k vertices to make a given graph (a) bipartite [17], (b) split [5], and (c) red/blue-split [7]. © 2008 Springer Berlin Heidelberg.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Journal	Data powered by TypesetTheoretical Computer Science
Publisher	Data powered by TypesetElsevier B.V.
ISSN	03043975
Open Access	No