Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
5 results
Search Results
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 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 induced colourful paths in triangle-free graphs(Elsevier B.V., 2019) Babu, J.; Basavaraju, M.; Sunil Chandran, L.S.; 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–Vitaver 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. © 2018 Elsevier B.V.Item Weak Total Coloring Conjecture and Hadwiger’s Conjecture on Total Graphs(Australian National University, 2024) Basavaraju, M.; Sunil Chandran, L.; Francis, M.C.; Naskar, A.The total graph of a graph G, denoted by T (G), is defined on the vertex set V (G) ∪ E(G) with c1, c2 ∈ V (G) ∪ E(G) adjacent whenever c1 and c2 are adjacent to (or incident on) each other in G. The total chromatic number χ′′ (G) of a graph G is defined to be the chromatic number of its total graph. The well-known Total Coloring Conjecture or TCC states that for every simple finite graph G having maximum degree ∆(G), χ′′ (G) ≤ ∆(G) + 2. In this paper, we consider two ways to weaken TCC: 1. Weak TCC: This conjecture states that for a simple finite graph G, χ′′ (G) = χ(T (G)) ≤ ∆(G)+3. While weak TCC is known to be true for 4-colorable graphs, it has remained open for 5-colorable graphs. In this paper, we settle this long pending case. 2. Hadwiger’s Conjecture for total graphs: We can restate TCC as a conjecture that proposes the existence of a strong χ-bounding function for the class of total graphs in the following way: If H is the total graph of a simple finite graph, then χ(H) ≤ ω(H) + 1, where ω(H) is the clique number of H. A natural way to relax this question is to replace ω(H) by the Hadwiger number η(H), the number of vertices in the largest clique minor of H. This leads to the Hadwiger’s Conjecture (HC) for total graphs: if H is a total graph then χ(H) ≤ η(H). We prove that this is true if H is the total graph of a graph with sufficiently large connectivity. It is known that (European Journal of Combinatorics, 76, 159–174,2019) if Hadwiger’s Conjecture is proved for the squares of certain special class of split graphs, then it holds also for the general case. The class of total graphs turns out to be the squares of graphs obtained by a natural structural modification of this type of split graphs. © The authors.Item Variants of the Gyárfás–Sumner conjecture: Oriented trees and rainbow paths(John Wiley and Sons Inc, 2025) Basavaraju, M.; Sunil Chandran, L.S.; Francis, M.C.; Murali, K.Given a finite family (Formula presented.) of graphs, we say that a graph (Formula presented.) is “ (Formula presented.) -free” if (Formula presented.) does not contain any graph in (Formula presented.) as a subgraph. We abbreviate (Formula presented.) -free to just “ (Formula presented.) -free” when (Formula presented.). A vertex-colored graph (Formula presented.) is called “rainbow” if no two vertices of (Formula presented.) have the same color. Given an integer (Formula presented.) and a finite family of graphs (Formula presented.), let (Formula presented.) denote the smallest integer such that any properly vertex-colored (Formula presented.) -free graph (Formula presented.) having (Formula presented.) contains an induced rainbow path on (Formula presented.) vertices. Scott and Seymour showed that (Formula presented.) exists for every complete graph (Formula presented.). A conjecture of N. R. Aravind states that (Formula presented.). The upper bound on (Formula presented.) that can be obtained using the methods of Scott and Seymour setting (Formula presented.) are, however, super-exponential. Gyárfás and Sárközy showed that (Formula presented.). For (Formula presented.), we show that (Formula presented.) and therefore, (Formula presented.). This significantly improves Gyárfás and Sárközy's bound and also covers a bigger class of graphs. We adapt our proof to achieve much stronger upper bounds for graphs of higher girth: we prove that (Formula presented.), where (Formula presented.). Moreover, in each case, our results imply the existence of at least (Formula presented.) distinct induced rainbow paths on (Formula presented.) vertices. Along the way, we obtain some new results on an oriented variant of the Gyárfás–Sumner conjecture. For (Formula presented.), let (Formula presented.) denote the orientations of (Formula presented.) in which one vertex has out-degree or in-degree (Formula presented.). We show that every (Formula presented.) -free oriented graph having a chromatic number at least (Formula presented.) and every bikernel-perfect oriented graph with girth (Formula presented.) having a chromatic number at least (Formula presented.) contains every oriented tree on at most (Formula presented.) vertices as an induced subgraph. © 2024 Wiley Periodicals LLC.