Sounaka Mishra

A domination coloring of a graph G is a proper vertex coloring with an additional condition that each vertex dominates a color class and each color class is dominated by a vertex. The minimum number of colors used in a domination coloring of G is denoted as χdd(G) and it is called domination chromatic number of G. In this paper, we give a polynomial-time characterization of graphs with domination chromatic number at most 3 and consider the approximability of a node deletion problem called minimum q-domination partization. Given a graph G, in the Minimumq-Domination Partization problem (in short Min-q-Domination-Partization), the objective is to find a vertex set S of minimum size such that χdd(G[V\ S]) ≤ q. For q= 2 , we prove that it is APX-complete and is best approximable within a factor of 2. For q= 3 , it is approximable within a factor of O(logn) and it is equivalent to minimum odd cycle transversal problem.

In this paper, we develop approximation algorithms for a few node deletion problems when the input is restricted to be a bipartite graph. We look at node deletion problems for non-trivial properties which can be characterized by forbidden structure which has a bounded intersection with both the bipartitions. The approximation factors obtained directly depend upon the size of the largest such intersection. Special instances of this general problem include problems such as the Minimum Chain Vertex Deletion, Minimum Dissociation Vertex Deletion, Minimum Bipartite Claw Vertex Deletion, Minimum Bi-complement Vertex Deletion and Minimum Bipartite Threshold Vertex Deletion problems. The algorithms are based upon the techniques of linear programming and iterative rounding. We also use the node deletion algorithms to marginally improve the trivial approximation factor for complementary problem of determining the size of the maximum sized vertex induced subgraph lying in the given graph class and prove the APX-completeness of all of these problems. © 2014 Elsevier B.V.

In this paper, we study the approximability of a variant of the Traveling Salesman Problem called the Biased-TSP. In the Biased-TSP, the edge cost function violates the triangle inequality in a “controlled” manner. We give a 7/2-factor approximation algorithm for this problem by a suitable modification of the double-tree heuristic.

In this paper, we study the path version of the Traveling Salesman Problem with the edge cost function satisfying a “relaxed” form of triangle inequality called the biased triangle inequality. We denote this problem as the Biased-TSP-Path. In this paper, we prove that the Biased-TSP-Path is approximable within a constant factor. Specifically, we design a 4-approximation algorithm by a suitable modification of the double-tree algorithm using effective shortcutting procedures.

A dominator coloring of a graph G is a proper vertex coloring with a domination property that each vertex dominates a color class. The minimum number of colors used in a dominator coloring of G is called dominator chromatic number of G and is denoted as χd(G). Graphs with χd(G) ≤ 3 have characterizations and such graphs can be recognized in polynomial time. However, for k ≥ 4, deciding whether χd(G) ≤ k is NP-hard. In this paper, we investigate the computational complexity of minimum q-dominator partization problem (Min-q-D-Partz). In Min-q-D-Partz, given a graph G, the objective is to find a vertex set S of minimum size such that χd(G[V â S]) ≤ q. We prove that Min-2-D-Partz is APX-complete and has a two-factor approximation algorithm. We also prove that Min-3-D-Partz cannot be approximated within any constant factor and can be approximated within a factor of O(log n).

In VCP4 problem, it is asked to find a set S⊆V of minimum size such that G[V\S] contains no path on 4 vertices, in a given graph G=(V,E). We prove that it is APX-complete for 3-regular graphs as well as 3-regular bipartite graphs. We show that a greedy based algorithm approximates VCP4 within a factor of 2 for regular graphs. We also show that VCP4 is APX-complete for K1, 4-free graphs and a local ratio based algorithm generates a solution which is within a factor of 3.

We consider approximability of two natural variants of classical dominating set problem, namely minimum majority monopoly and minimum signed domination. In the minimum majority monopoly problem, the objective is to find a smallest size subset X≤V in a given graph G=(V,E) such that

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.

We consider approximability of two optimization problems called Minimum Open k-Monopoly (Min-Open-k-Monopoly) and Minimum Partial Open k-Monopoly (Min-P-Open-k-Monopoly), where k is a fixed positive integer. The objective, in Min-Open-k-Monopoly, is to find a minimum cardinality vertex set S⊆V in a given graph G = (V,E) such that |N(v)∩S|≥12|N(v)|+k, for every vertex v∈V. On the other hand, given a graph G = (V,E), in Min-P-Open-k-Monopoly it is required to find a minimum cardinality vertex set S⊆ V such that |N(v)∩S|≥12|N(v)|+k, for every v∈V∖S. We prove that Min-Open-k-Monopoly and Min-P-Open-k-Monopoly are approximable within a factor of O(log n). Then, we show that these two problems cannot be approximated within a factor of (13−ε)lnn and (14−ε)lnn, respectively, for any > 0, unless NP⊆Dtime(nO(loglogn)). For 4-regular graphs, we prove that these two problems are APX-complete. Min-Open-1-Monopoly can be approximated within a factor of 2621≈1.2381 where as Min-P-Open-1-Monopoly can be approximated within a factor of 1.65153. For k ≥ 2, we also present approximation algorithms for these two problems for (2k + 2)-regular graphs.

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].