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

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.

In this paper, we investigate the approximability of two node deletion problems. Given a vertex weighted graph G=(V,E) and a specified, or "distinguished" vertex p∈V, MDD(min) is the problem of finding a minimum weight vertex set S⊆V\{p} such that p becomes the minimum degree vertex in G[V\S]; and MDD(max) is the problem of finding a minimum weight vertex set S⊆V\{p} such that p becomes the maximum degree vertex in G[V\S]. These are known NP-complete problems and they have been studied from the parameterized complexity point of view in [1]. Here, we prove that for any ε>0, both the problems cannot be approximated within a factor (1-ε)log n, unless NP⊆Dtime(nlog log n). We also show that for any ε>0, MDD(min) cannot be approximated within a factor (1-ε)log n on bipartite graphs, unless NP⊆Dtime(nlog log n), and that for any ε>0, MDD(max) cannot be approximated within a factor (1/2-ε)log n on bipartite graphs, unless NP⊆Dtime(nlog log n). We give an O(log n) factor approximation algorithm for MDD(max) on general graphs, provided the degree of p is O(log n). We then show that if the degree of p is n-O(log n), a similar result holds for MDD(min). We prove that MDD(max) is APX-complete on 3-regular unweighted graphs and provide an approximation algorithm with ratio 1.583 when G is a 3-regular unweighted graph. In addition, we show that MDD(min) can be solved in polynomial time when G is a regular graph of constant degree.