Search

A k -role coloring α of a graph G is an assignment of k colors to the vertices of G such that every color is used at least once and if any two vertices are assigned the same color, then their neighborhood are assigned the same set of colors. By definition, every graph on n vertices admits an n -role coloring. While for every graph on n vertices, it is trivial to decide if it admits a 1-role coloring, determining whether a graph admits a k -role coloring is a notoriously hard problem for k ≥ 2. In fact, it is known that k - Role coloring is NP -complete for k ≥ 2 on general graph class. There has been extensive research on the complexity of k - role coloring on various hereditary graph classes. Furthering this direction of research, we show that k - Role coloring is NP -complete on bipartite graphs for k ≥ 3 (while it is trivial for k = 2). We complement the hardness result by characterizing 3-role colorable bipartite chain graphs, leading to a polynomial time algorithm for 3- Role coloring for this class of graphs. We further show that 2- Role coloring is NP -complete for graphs that are d vertices or edges away from the class of bipartite graphs, even when d = 1. [ABSTRACT FROM AUTHOR]

In the Geometric Conflict Free Covering , we are given a set of points P , a set of closed geometric objects O and a conflict graph CG O with O as vertex set. An edge (O i , O j) in CG O denotes conflict between O i and O j and at most one among these can be part of any feasible solution. A set of objects is conflict free if they form an independent set in CG O. The objective is to find a conflict free set of objects that maximizes the number of points covered. We consider the Unit Interval Covering where P is a set of points on the real line, and O is a set of closed unit-length intervals. The objective is to find a smallest subset of given intervals that covers P. We prove that for an arbitrary conflict graph the problem is Poly-APX -hard. We present an approximation algorithm for a special class of conflict graphs with a bounded graph parameter Clique Partition. A Clique Partition of the graph G is a set of cliques such that every vertex in the graph is part of exactly one clique. For any Clique Partition C , we define the Clique Partition Graph, G C with vertex set C and there is an edge (C i , C j) in G C , if and only if there exist two vertices in G , v a ∈ C i and v b ∈ C j such that there is an edge (v a , v b) in G. For a graph G , Clique Partition Chromatic Number is defined as the minimum chromatic number among all possible Clique Partitions of the Clique Partition Graph. In this paper, we consider those graph classes for which Clique Partition Chromatic Number can be computed in polynomial time. We present a 4 γ approximation algorithm for conflict graphs having Clique Partition Chromatic Number γ. We show that unit interval graphs and unit disk graphs have constant Clique Partition Chromatic Number while for chordal graphs, it is bounded by log ⁡ n. Note that, Clique Partition Chromatic Number is less than or equal to the chromatic number. Thus our algorithm achieves a constant approximation factor for graphs with constant chromatic number (e.g. planar graphs). This is the first result regarding the approximability in Geometric Conflict Free Covering. [ABSTRACT FROM AUTHOR]

It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most k vertices whose deletion results in a chordal graph when parameterized by k. While this investigation fits naturally into the recent trend of what is called 'structural parameterizations', here we assume that the deletion set is not given. One method to solve them is to compute a k-sized or an approximate (f(k) sized, for a function f) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least k O (k) n O (1) running time when we use the known parameterized or approximation algorithms for finding a k-sized chordal deletion set on an n vertex graph. In this work, we design 2 O (k) n O (1) time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in 2 O (k) n O (1) time where each bag is a union of four cliques and O (k) vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are, what are sometimes called permissive in the sense that given an integer k, they detect whether the graph has no chordal vertex deletion set of size at most k or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the strong exponential time hypothesis. [ABSTRACT FROM AUTHOR]

Vertex deletion problems on graphs involve finding a set of minimum number of vertices whose deletion results in a graph with some specific property. In a recent study on vertex deletion problems on split graphs, it was shown that transforming a split graph to a block graph or a threshold graph using minimum number of vertex deletions is NP -hard. We call the decision version of these problems as Split to Block Vertex Deletion (SBVD) and Split to Threshold Vertex Deletion (STVD), respectively. In this paper, we study the parameterized complexity of these problems with the number of vertex deletions, k , as a parameter. These problems are implicit 4- Hitting Set and thus admit an algorithm with running time O ⋆ (3.0755 k) , a kernel with O (k 3) vertices, and a 4-approximation algorithm. In this paper, we exploit the structural properties of the concerned graph classes and obtain a kernel for SBVD with O (k 2) vertices and FPT algorithms for SBVD and STVD with running times O ⋆ (2.3028 k) and O ⋆ (2.7913 k) , respectively. We further give improved approximation algorithms for SBVD and STVD. [ABSTRACT FROM AUTHOR]

The input for the Geometric Coverage problem consists of a pair Σ = (P , R) , where P is a set of points in R d and R is a set of subsets of P defined by the intersection of P with some geometric objects in R d . Motivated by what are called choice problems in geometry, we consider a variation of the Geometric Coverage problem where there are conflicts on the covering objects that precludes some objects from being part of the solution if some others are in the solution. As our first contribution, we propose two natural models in which the conflict relations are given: (a) by a graph on the covering objects, and (b) by a representable matroid on the covering objects. Our main result is that as long as the conflict graph has bounded arboricity there is a parameterized reduction to the conflict-free version. As a consequence, we have the following results when the conflict graph has bounded arboricity. (1) If the Geometric Coverage problem is fixed parameter tractable (FPT), then so is the conflict free version. (2) If the Geometric Coverage problem admits a factor α -approximation, then the conflict free version admits a factor α -approximation algorithm running in FPT time. As a corollary to our main result we get a plethora of approximation algorithms that run in FPT time. Our other results include an FPT algorithm and a hardness result for conflict-free version of Covering Points by Intervals. The FPT algorithm is for the case when the conflicts are given by a representable matroid. We prove that conflict-free version of Covering Points by Intervals does not admit an FPT algorithm, unless FPT =W[1], for the family of conflict graphs for which the Independent Set problem is W[1]-hard. [ABSTRACT FROM AUTHOR]

Frèchet distance is an important geometric measure that captures the distance between two curves or more generally point sets. In this paper, we consider a natural variant of Fréchet distance problem with multiple choice, provide an approximation algorithm and address its parameterized and kernelization complexity. A multiple choice problem consists of a set of color classes Q={Q1,Q2,…,Qn}, where each class Qi consists of a pair of points Qi={qi,qi¯}. We call a subset A⊂{qi,qi¯:1≤i≤n} conflict-free if A contains at most one point from each color class. The standard objective in multiple choice problem is to select a conflict-free subset that optimizes a given function. Given a line-segment ℓ and a set Q of a pair of points in R2, our objective is to find a conflict-free subset that minimizes the Fréchet distance between ℓ and the point set, where the minimum is taken over all possible conflict-free subsets. We first show that this problem is NP-hard, and provide a 3-approximation algorithm. Then we develop a simple randomized FPT algorithm for the problem when parametrized by the solution size, which is later derandomized using universal family of sets. We believe that our derandomization technique can be of independent interest, and can be used to solve other parameterized multiple choice problems. The randomized algorithm runs in O(2knlog2n) time, and the derandomized deterministic algorithm runs in 2kkO(logk)nlog2n time, where k, the parameter, is the number of elements in the conflict-free subset solution. Finally we present a simple branching algorithm for the problem running in O(2knlogn) time. We also show that the problem does not have a polynomial sized kernel under standard complexity theoretic assumptions. [ABSTRACT FROM AUTHOR]