Browsing by Author "Ramanujan, M.S."

Filter results by typing the first few letters
Now showing 1 - 4 of 4
  • No Thumbnail Available
    Item
    On the kernelization complexity of string problems
    (Elsevier B.V., 2018) Basavaraju, M.; Panolan, F.; Rai, A.; Ramanujan, M.S.; Saurabh, S.
    In the CLOSEST STRING problem we are given an alphabet ?, a set of strings S={s1,s2,…,sk} over ? such that |si|=n and an integer d. The objective is to check whether there exists a string s over ? such that dH(s,si)?d, i?{1,…,k}, where dH(x,y) denotes the number of places strings x and y differ at. CLOSEST STRING is a prototype string problem. This problem together with several of its variants such as DISTINGUISHING STRING SELECTION and CLOSEST SUBSTRING have been extensively studied from parameterized complexity perspective. These problems have been studied with respect to parameters that are combinations of k, d, |?| and n. However, surprisingly the kernelization question for these problems (for the versions when they admit fixed-parameter tractable algorithms) is not studied at all. In this paper we fill this gap in the literature and do a comprehensive study of these problems from kernelization complexity perspective. We settle almost all the problems by either obtaining a polynomial kernel or showing that the problem does not admit a polynomial kernel under a standard assumption in complexity theory. © 2018 Elsevier B.V.
  • No Thumbnail Available
    Item
    Parameterized algorithms for survivable network design with uniform demands
    (2018) Bang-Jensen, J.; Basavaraju, M.; Klinkby, K.V.; Misra, P.; Ramanujan, M.S.; Saurabh, S.; Zehavi, M.
    In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u; v 2 V (G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call ?-Edge Connected Subgraph ( ?-ECS). In this problem, the input is a ?-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also ?-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace ?-edge connectivity with ?-vertex connectivity we get the ?-Vertex Connected Subgraph ( ?-VCS) problem. We show that ?-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k)jV (G)jO(1). We follow up on this result and obtain a polynomial compression for ?-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that ?-VCS is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs. � Copyright 2018 by SIAM.
  • No Thumbnail Available
    Item
    Parameterized algorithms for survivable network design with uniform demands
    (Association for Computing Machinery acmhelp@acm.org, 2018) Bang-Jensen, J.; Basavaraju, M.; Klinkby, K.V.; Misra, P.; Ramanujan, M.S.; Saurabh, S.; Zehavi, M.
    In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u; v 2 V (G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call λ-Edge Connected Subgraph ( λ-ECS). In this problem, the input is a λ-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also λ-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace λ-edge connectivity with λ-vertex connectivity we get the λ-Vertex Connected Subgraph ( λ-VCS) problem. We show that λ-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k)jV (G)jO(1). We follow up on this result and obtain a polynomial compression for λ-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that λ-VCS is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs. © Copyright 2018 by SIAM.
  • No Thumbnail Available
    Item
    Partially polynomial kernels for set cover and test cover
    (Society for Industrial and Applied Mathematics Publications support@jstor.org, 2016) Basavaraju, M.; Francis, M.C.; Ramanujan, M.S.; Saurabh, S.
    An instance of the (n-k)-Set Cover or the (n-k)-Test Cover problems is of the form (U, S, k), where U is a set with n elements, S ? 2U with |S| = m, and k is the parameter. The instance is a Yes-instance of (n - k)-Set Cover if and only if there exists S' ? S with |S'| ? n - k such that every element of U is contained in some set in S'. Similarly, it is a Yes-instance of (n - k)-Test Cover if and only if there exists S' ? S with |S'| ? n - k such that for any pair of elements from U, there exists a set in S' that contains one of them but not the other. It is known in the literature that both (n - k)-Set Cover and (n - k)-Test Cover do not admit polynomial kernels (under some well-known complexity theoretic assumptions). However, in this paper we show that they do admit \partially polynomial kernels": we give polynomial time algorithms that take as input an instance (U, S, k) of (n - k)-Set Cover (respectively, (n - k)-Test Cover) and return an equivalent instance (U, S, k) of (n-k)-Set Cover (respectively, (n-k)-Test Cover) with k ? k and |?| = O(k2) (respectively, |?| = O(k7)). These results allow us to generalize, improve, and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain \sparsity properties." Using a part of our partial kernelization algorithm for (n - k)-Set Cover, we also get an improved fixed-parameter tractable algorithm for this problem which runs in time O(4kkO(1)(m + n) + mn) improving over the previous best of O(8k+o(k)(m+n)O(1)). On the other hand, the partially polynomial kernel for (n-k)-Test Cover gives an algorithm with running time O(2O(k2)(m + n)O(1)). We believe such an approach could also be useful for other covering problems. © © by SIAM.