Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
17 results
Search Results
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.Item Ramsey Numbers for Line Graphs(Springer, 2020) Abbasi, H.; Basavaraju, M.; Gurushankar, E.; Jivani, Y.; Srikanth, D.Given a graph, the classical Ramsey number R(k, l) is the least number of vertices that need to be in the graph for the existence of a clique of size k or an independent set of size l. Finding R(k, l) exactly has been a notoriously hard problem. Even R(k, 3) has not been determined for all values of k. Hence finding the Ramsey number for subclasses of graphs is an interesting question. It is known that even for claw-free graphs, finding Ramsey number is as hard as for general graphs for infinite number of cases. Line graphs are an important subclass of claw-free graphs. The question with respect to line graph L(G) is equivalent to the minimum number of edges the underlying graph G needs to have for the existence of a vertex with degree k or a matching of size l. Chvátal and Hanson determined this exactly for line graphs of simple graphs. Later Balachandran and Khare gave the same bounds with a different proof. In this paper we find Ramsey numbers for line graph of multi graphs thereby extending the results of Chvátal and Hanson. Here we determine the maximum number of edges that a multigraph can have, when its matching number, multiplicity, and maximum degree are bounded, and characterize such graphs. © 2020, Springer Nature Switzerland AG.Item The Linear Arboricity Conjecture for 3-Degenerate Graphs(Springer Science and Business Media Deutschland GmbH info@springer-sbm.com, 2020) Basavaraju, M.; Bishnu, A.; Francis, M.; Pattanayak, D.A k-linear coloring of a graph G is an edge coloring of G with k colors so that each color class forms a linear forest—a forest whose each connected component is a path. The linear arboricity χl′(G) of G is the minimum integer k such that there exists a k-linear coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every graph G, χl′(G)≤⌈Δ(G)+12⌉ where Δ(G) is the maximum degree of G. We prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture for triangle-free planar graphs. Our proof also yields an O(n)-time algorithm that partitions the edge set of any 3-degenerate graph G on n vertices into at most ⌈Δ(G)+12⌉ linear forests. Since χl′(G)≥⌈Δ(G)2⌉ for any graph G, the partition produced by the algorithm differs in size from the optimum by at most an additive factor of 1. © 2020, Springer Nature Switzerland AG.Item Vehicular Pollution and Its Relationship with Meteorological Variables at Toll Plaza During Paryaya Festival in Udupi, Karnataka(Springer Science and Business Media Deutschland GmbH, 2024) Charly, T.; Basavaraju, M.; Mulangi, R.H.The quantification of both air pollutants and noise is important to understand the impact of festival on pollution at toll plaza. Toll plazas can cause deterioration of air quality due to increased emission of pollutants caused by stop and go process. The present study was conducted at a toll plaza in front of National Institute of Technology, Karnataka, which is 39 kms from Udupi, Karnataka, to assess the impact of vehicular movement due to Paryaya festival, which was on the third week of January 2020 at Udupi, on noise and air pollution at study area. Data regarding meteorological parameters and traffic volume were also considered during the study. Experiments were carried out at toll plaza for one week, including pre- and post-festival days. In this study, a spearman correlation matrix between air pollutants and meteorological parameters (temperature, pressure, precipitable water content, relative humidity, and wind speed) were also investigated. The concentration of air pollutants (TSPM, SO2, CO2) and noise were more on the day of festival as the number of vehicles plying on the road was higher in number. Maximum positive correlation was observed between concentration of CO and precipitable water content (Ï â€‰= 0.900) and minimum between SO2 and precipitable water content (Ï â€‰= 0.000). Precipitable water content was positively correlated with all air pollutants (TSPM, NO2, CO, and CO2), and no correlation was observed with SO2. The results show the impact of increase in vehicular movement due to festival on the quality of ambient air and role of meteorology on urban air pollution. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.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.Item Separation Dimension of Graphs and Hypergraphs(Springer New York LLC barbara.b.bertram@gsk.com, 2016) Basavaraju, M.; Sunil Chandran, L.S.; Golumbic, M.C.; Mathew, R.; Rajendraprasad, D.Separation dimension of a hypergraph H, denoted by ?( H) , is the smallest natural number k so that the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the boxicity of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension. In this paper, we study the separation dimension of hypergraphs and graphs. © 2015, Springer Science+Business Media New York.Item Maximal Induced Matchings in Triangle-Free Graphs(Wiley-Liss Inc. info@wiley.com, 2016) Basavaraju, M.; Heggernes, P.; van 't'Hof, P.; Saei, R.; Villanger, Y.An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every n-vertex graph has at most (Formula presented.) maximal induced matchings, and this bound is the best possible. We prove that every n-vertex triangle-free graph has at most (Formula presented.) maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K3, 3. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time (Formula presented.), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph. © 2015 Wiley Periodicals, Inc.Item On Induced Colourful Paths in Triangle-free Graphs(Elsevier B.V., 2017) Babu, J.; Basavaraju, M.; Sunil Chandran, L.; Francis, M.C.Given a graph G=(V,E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy Theorem that every properly coloured graph contains a colourful path on ?(G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on ?(G) vertices and prove its correctness when the girth of G is at least ?(G). Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if ?(G)?f(k), then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G. © 2017 Elsevier B.V.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.Item Separation dimension and sparsity(Wiley-Liss Inc. info@wiley.com, 2018) Alon, N.; Basavaraju, M.; Sunil Chandran, L.S.; Mathew, R.; Rajendraprasad, D.The separation dimension ???(G) of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in Rk so that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family F of total orders of V(G), such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge-density of a graph on one another. On one hand, we show that the maximum separation dimension of a k-degenerate graph on n vertices is O(k lg lg n) and that there exists a family of 2-degenerate graphs with separation dimension ?(lg lg n). On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that n-vertex graphs with separation dimension s have at most 3(4 lg n)s?2 edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound. © 2018 Wiley Periodicals, Inc.