Neeldhara Misra

Abstract: Preprocessing (data reduction or kernelization) to reduce instance size is one of the most commonly deployed heuristics in the implementation practice to tackle computationally hard problems. However, a systematic theoretical study of them remained elusive so far. One of the reasons for this is that if an input to an $NP$-hard problem can be processed in polynomial time to an equivalent one of smaller size in general, then the preprocessing algorithm can be used to actually {\it solve} the problem in polynomial time proving $P = NP$, which is expected to be unlikely. However the situation regarding systematic study changed drastically with the advent of parameterized complexity. Parameterized complexity provides a natural framework to analyse preprocessing algorithms. In a parameterized problem, every instance $x$ comes with a positive integer, or parameter, $k$. The problem is said to admit a kernel if, in polynomial time, we can reduce the size of the instance $x$ to a function in $k$, while preserving the answer. The central notion in parameterized complexity is {\em fixed parameter tractability (FPT)}, which is the notion of solvability in $f(k)\cdot p(|x|)$ time for any given instance $(x,k)$, where $f$ is an arbitrary function of the parameter $k$ and $p$ is a polynomial in the input size $|x|$. It is folklore that a parameterized problem $\Pi$ is fixed-parameter tractable if and only if there exists a computable function $g(k)$ such that $\Pi$ admits a kernel of size $g(k)$. However, the kernels obtained by this theoretical result are usually of exponential (or even worse) sizes, while problem-specific data reductions often achieve quadratic- or even linear-size kernels. So a natural question for any concrete FPT problem is whether it admits polynomial time kernelization to a problem kernel that in the worst case is bounded by a polynomial function of the parameter. Despite several attempts, there are fixed-parameter tractable problems that have only exponential sized kernels. An explanation was provided in a paper by Bodlaender et al. where it was shown that unless $coNP \subseteq NP/poly$, there are fixed-parameter tractable problems that cannot have a polynomial sized kernel. This triggered further work on showing lower bounds of kernels, and this article surveys recent developments in the area starting from the framework developed in the paper by Bodlaender et al..

Abstract: In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring, Hamilton Path, Minimum Dominating Set, Minimum Bandwidth or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things: (1) We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G)�k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O*(f(k)). (2) The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions.

Abstract:

Abstract: We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G = (V, E) and an integer k, decide whether there exists F � V , |F | � k, such that G[V F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2O(k) nO(1)) on general graphs and in time O(2O(sqrt(k) log k) nO(1)) on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.

Abstract: In the Connected Dominating Set problem we are given as input a graph $G$ and a positive integer $k$, and are asked if there is a subset $S$ of at most $k$ vertices of $G$ such that $S$ is a dominating set of $G$ and the subgraph induced by $S$ is connected. This is a basic connectivity problem that is known to be NP-complete, and it has been extensively studied using several algorithmic approaches. In this paper, we explore the effect of excluding short cycles, as a subgraph, on the kernelization complexity of this problem.

Abstract: The problem of finding a satisfying assignment for a 2-SAT formula that minimizes the number of variables that are set to 1 (min ones 2�sat) is NP-complete. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from min ones 2�sat to vertex cover without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k variables kernel subsuming these results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover.

Abstract: In the Imbalance Minimization problem we are given a graph G = (V;E) and an integer b and asked whether there is an ordering of V such that the sum of the imbalance of all the vertices is at most b. The imbalance of a vertex v is the absolute value of the difference between the number of neighbors to the left and right of v. The problem is also known as the Balanced Vertex Ordering problem and it finds many applications in graph drawing. We show that this problem is fixed parameter tractable and provide an algorithm that runs in time 2^O(b log b)n^O(1). This resolves an open problem of Kara et al. [COCOON 2005].

Abstract: The Colorful Motif problem asks if, given a vertex-colored graph G, there exists a subset S of vertices of G such that the graph induced by G on S is connected and contains every color in the graph exactly once. The problem is motivated by applications in computational biology and is also well-studied from the theoretical point of view. In particular, it is known to be NP-complete even on trees of maximum degree three [Fellows et al, ICALP 2007]. In their pioneering paper that introduced the color-coding technique, Alon et al. [STOC 1995] show, inter alia, that the problem is FPT on general graphs. More recently, Cygan et al. [WG 2010] showed that Colorful Motif is NP-complete on comb graphs, a special subclass of the set of trees of maximum degree three. They also showed that the problem is not likely to admit polynomial kernels on forests. We continue the study of the kernelization complexity of the Colorful Motif problem restricted to simple graph classes. Surprisingly, the infeasibility of polynomial kernelization persists even when the input is restricted to comb graphs. We demonstrate this by showing a simple but novel composition algorithm. Further, we show that the problem restricted to comb graphs admits polynomially many polynomial kernels. To our knowledge, there are very few examples of problems with many polynomial kernels known in the literature. We also show hardness of polynomial kernelization for certain variants of the problem on trees; this rules out a general class of approaches for showing many polynomial kernels for the problem restricted to trees. Finally, we show that the problem is unlikely to admit polynomial kernels on another simple graph class, namely the set of all graphs of diameter two. As an application of our results, we settle the classical complexity of Connected Dominating Set on graphs of diameter two � specifically, we show that it is NP-complete.

Abstract: We show, by a non-trivial application of the color-coding method of Alon et al.[2], that Budgeted Unique Coverage (a variant of Set Cover) is fixed-parameter tractable, answering an open problem posed in [13]. We also give improved fixed-parameter tractable algorithms for two special cases of Budgeted Unique Coverage: Unique Coverage (the unweighted version) and Budgeted Max Cut. To derandomize our algorithms we use an interesting variation of k-perfect hash families known as (k,s)-hash families which were studied by Alon et al.[1] in the context of a class of codes called parent identifying codes [3]. In this setting, for every s-element subset S of the universe, and every k-element subset X of S, there exists a function that maps X injectively and maps the remaining elements of S into a different range. We give several bounds on the size of (k,s)-hash families. We believe that our application of color-coding may be used for other problems and that this is the first application of (k,s)-hash families to a problem outside the domain of coding theory.

Abstract: In the framework of parameterized complexity, one of the most commonly used structural parameters is the treewidth of the input graph. The reason for this is that most natural graph problems turn out to be fixed parameter tractable when parameterized by treewidth. However, Graph Layout problems are a notable exception. In particular, no fixed parameter tractable algorithms are known for the Cutwidth, Bandwidth, Imbalance and Distortion problems parameterized by treewidth. In fact, Bandwidth remains NP-complete even restricted to trees. A possible way to attack graph layout problems is to consider structural parameterizations that are stronger than treewidth. In this paper we study graph layout problems parameterized by the size of the minimum vertex cover of the input graph. We show that all the mentioned problems are fixed parameter tractable. Our basic ingredient is a classical algorithm for Integer Linear Programming when parameterized by dimension, designed by Lenstra and later improved by Kannan. We hope that our results will serve to re-emphasize the importance and utility of this algorithm.

Abstract: In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. �Classroom� is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science.