2019 [ nach oben ]

• 
  Issac, Davis; Chandran, L. Sunil; Zhou, SanmingHadwiger's conjecture for squares of 2-trees. European Journal of Combinatorics 2019
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Hadwiger's conjecture asserts that any graph contains a clique minor with order no less than the chromatic number of the graph. We prove that this well-known conjecture is true for all graphs if and only if it is true for squares of split graphs. This observation implies that Hadwiger's conjecture for squares of chordal graphs is as difficult as the general case, since chordal graphs are a superclass of split graphs. Then we consider 2-trees which are a subclass of each of planar graphs, 2-degenerate graphs and chordal graphs. We prove that Hadwiger's conjecture is true for squares of 2-trees. We achieve this by proving the following stronger result: If G is the square of a 2 tree, then G has a clique minor of size \(\chi(G)\), where each branch set is a path.
  @article{noauthororeditor, abstract = {Hadwiger's conjecture asserts that any graph contains a clique minor with order no less than the chromatic number of the graph. We prove that this well-known conjecture is true for all graphs if and only if it is true for squares of split graphs. This observation implies that Hadwiger's conjecture for squares of chordal graphs is as difficult as the general case, since chordal graphs are a superclass of split graphs. Then we consider 2-trees which are a subclass of each of planar graphs, 2-degenerate graphs and chordal graphs. We prove that Hadwiger's conjecture is true for squares of 2-trees. We achieve this by proving the following stronger result: If G is the square of a 2 tree, then G has a clique minor of size \(\chi(G)\), where each branch set is a path.}, author = {Issac, Davis and Chandran, L. Sunil and Zhou, Sanming}, booktitle = {European Journal of Combinatorics}, keywords = {sys:relevantfor:ae davisissac eujc lsunilchandran sanmingzhou year2019}, title = {Hadwiger's conjecture for squares of 2-trees}, volume = 76, year = 2019 }

2018 [ nach oben ]

• 
  Issac, Davis; Bhattacharya, Anup; Kumar, Amit; Jaiswal, RageshSampling in space restricted settings. Algorithmica 2018: 1439-1458
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  Space efficient algorithms play an important role in dealing with large amount of data. In such settings, one would like to analyze the large data using small amount of “working space”. One of the key steps in many algorithms for analyzing large data is to maintain a (or a small number) random sample from the data points. In this paper, we consider two space restricted settings-(i) the streaming model, where data arrives over time and one can use only a small amount of storage, and (ii) the query model, where we can structure the data in low space and answer sampling queries. In this paper, we prove the following results in the above two settings: \begin{itemize item In the streaming setting, we would like to maintain a random sample from the elements seen so far. We prove that one can maintain a random sample using \( \mathcal{O(\log n) \) random bits and \( \mathcal{O(\log n) \) bits of space, where n is the number of elements seen so far. We can extend this to the case when elements have weights as well. item In the query model, there are n elements with weights \(w_1, \dots, w_n \) (which are w-bit integers) and one would like to sample a random element with probability proportional to its weight. Bringmann and Larsen (STOC 2013) showed how to sample such an element using \(n \omega + 1\) bits of space (whereas, the information theoretic lower bound is \(n \omega \)). We consider the approximate sampling problem, where we are given an error parameter \( \varepsilon \), and the sampling probability of an element can be off by an \( \varepsilon \) factor. We give matching upper and lower bounds for this problem. \end{itemize
  @article{ibkj-ssrs-2018, abstract = {Space efficient algorithms play an important role in dealing with large amount of data. In such settings, one would like to analyze the large data using small amount of “working space”. One of the key steps in many algorithms for analyzing large data is to maintain a (or a small number) random sample from the data points. In this paper, we consider two space restricted settings-(i) the streaming model, where data arrives over time and one can use only a small amount of storage, and (ii) the query model, where we can structure the data in low space and answer sampling queries. In this paper, we prove the following results in the above two settings: \begin{itemize} \item In the streaming setting, we would like to maintain a random sample from the elements seen so far. We prove that one can maintain a random sample using \( \mathcal{O}(\log n) \) random bits and \( \mathcal{O}(\log n) \) bits of space, where n is the number of elements seen so far. We can extend this to the case when elements have weights as well. \item In the query model, there are n elements with weights \(w_1, \dots, w_n \) (which are w-bit integers) and one would like to sample a random element with probability proportional to its weight. Bringmann and Larsen (STOC 2013) showed how to sample such an element using \(n \omega + 1\) bits of space (whereas, the information theoretic lower bound is \(n \omega \)). We consider the approximate sampling problem, where we are given an error parameter \( \varepsilon \), and the sampling probability of an element can be off by an \( \varepsilon \) factor. We give matching upper and lower bounds for this problem. \end{itemize}}, author = {Issac, Davis and Bhattacharya, Anup and Kumar, Amit and Jaiswal, Ragesh}, booktitle = {Algorithmica}, keywords = {sys:relevantfor:ae algorithmica amitkumar anupbhattacharya davisissac rageshjaiswal year2018}, month = {June}, pages = {1439-1458}, title = {Sampling in space restricted settings}, volume = 80, year = 2018 }
• 
  Issac, Davis; Chandran, L. Sunil; Cheung, Yuen KuengSpanning tree congestion and computation of gyori lovasz partition. International Colloquium on Automata, Languages, and Programming (ICALP) 2018
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, it seeks a spanning tree with no tree-edge routing too many of the original edges. For any general connected graph with n vertices and m edges, we show that its STC is at most \( \mathcal{O(\sqrt{mn}) \), which is asymptotically optimal since we also demonstrate graphs with STC at least \( \Omega(\sqrt{mn}) \). We present a polynomial-time algorithm which computes a spanning tree with congestion \( \mathcal{O(\sqrt{mn}) \log n \) \( \mathcal{O(\sqrt{mn} \log n ) \). We also present another algorithm for computing a spanning tree with congestion \( \mathcal{O(\sqrt{mn}) \); this algorithm runs in sub-exponential time when \(m = \omega(n \log^2 n ) \). For achieving the above results, an important intermediate theorem is generalized Györi-Lovász theorem. Chen et al. [Jiangzhuo Chen et al., 2007] gave a non-constructive proof. We give the first elementary and constructive proof with a local search algorithm of running time \( \mathcal{O^*( 4^n ) \). We discuss some consequences of the theorem concerning graph partitioning, which might be of independent interest. We also show that for any graph which satisfies certain expanding properties, its STC is at most \( \mathcal{O^*(n) \), and a corresponding spanning tree can be computed in polynomial time. We then use this to show that a random graph has STC \( \Theta(n) \) with high probability.
  @inproceedings{icc-stccglp-2018, abstract = {We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, it seeks a spanning tree with no tree-edge routing too many of the original edges. For any general connected graph with n vertices and m edges, we show that its STC is at most \( \mathcal{O}(\sqrt{mn}) \), which is asymptotically optimal since we also demonstrate graphs with STC at least \( \Omega(\sqrt{mn}) \). We present a polynomial-time algorithm which computes a spanning tree with congestion \( \mathcal{O}(\sqrt{mn}) \log n \) \( \mathcal{O}(\sqrt{mn} \log n ) \). We also present another algorithm for computing a spanning tree with congestion \( \mathcal{O}(\sqrt{mn}) \); this algorithm runs in sub-exponential time when \(m = \omega(n \log^2 n ) \). For achieving the above results, an important intermediate theorem is generalized Györi-Lovász theorem. Chen et al. [Jiangzhuo Chen et al., 2007] gave a non-constructive proof. We give the first elementary and constructive proof with a local search algorithm of running time \( \mathcal{O}^*( 4^n ) \). We discuss some consequences of the theorem concerning graph partitioning, which might be of independent interest. We also show that for any graph which satisfies certain expanding properties, its STC is at most \( \mathcal{O}^*(n) \), and a corresponding spanning tree can be computed in polynomial time. We then use this to show that a random graph has STC \( \Theta(n) \) with high probability.}, author = {Issac, Davis and Chandran, L. Sunil and Cheung, Yuen Kueng}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {davisissac icalp lsunilchandran year2018 yuenkuencheung}, title = {Spanning tree congestion and computation of gyori lovasz partition}, year = 2018 }
• 
  Issac, Davis; van Leeuwen, Erik Jan; Das, Anita; Chandran, L. SunilAlgorithms and bounds for very strong rainbow coloring. Latin American Symposium on Theoretical Informatics Conference (LATIN) 2018
  [ Abstract ] [ BibTeX ] [ Download ]
   
  A well-studied coloring problem is to assign colors to the edges of a graph G so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number (\(\mathbf{src(G) \)) of the graph. When proving upper bounds on \(\mathbf{src(G) \), it is natural to prove that a coloring exists where, for every shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call very strong rainbow connection number (\(\mathbf{vsrc(G) \)). In this paper, we give upper bounds on \(\mathbf{vsrc(G) \) for several graph classes, some of which are tight. These immediately imply new upper bounds on \(\mathbf{src(G) \) for these classes, showing that the study of \(\mathbf{vsrc(G) \) enables meaningful progress on bounding \(\mathbf{src(G) \). Then we study the complexity of the problem to compute \(\mathbf{vsrc(G) \), particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that \(\mathbf{vsrc(G) \) can be computed in polynomial time on cactus graphs; in contrast, this question is still open for \(\mathbf{src(G) \). We also observe that deciding whether \(\mathbf{vsrc(G) = k \) is fixed-parameter tractable in k and the treewidth of G. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether \(\mathbf{vsrc(G) \leq 3 \) nor to approximate \(\mathbf{vsrc(G) \) within a factor \( n^1-\varepsilon \), unless P = NP.
  @inproceedings{ildc-abvsrc-2018, abstract = {A well-studied coloring problem is to assign colors to the edges of a graph G so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number (\(\mathbf{src}(G) \)) of the graph. When proving upper bounds on \(\mathbf{src}(G) \), it is natural to prove that a coloring exists where, for every shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call very strong rainbow connection number (\(\mathbf{vsrc}(G) \)). In this paper, we give upper bounds on \(\mathbf{vsrc}(G) \) for several graph classes, some of which are tight. These immediately imply new upper bounds on \(\mathbf{src}(G) \) for these classes, showing that the study of \(\mathbf{vsrc}(G) \) enables meaningful progress on bounding \(\mathbf{src}(G) \). Then we study the complexity of the problem to compute \(\mathbf{vsrc}(G) \), particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that \(\mathbf{vsrc}(G) \) can be computed in polynomial time on cactus graphs; in contrast, this question is still open for \(\mathbf{src}(G) \). We also observe that deciding whether \(\mathbf{vsrc}(G) = k \) is fixed-parameter tractable in k and the treewidth of G. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether \(\mathbf{vsrc}(G) \leq 3 \) nor to approximate \(\mathbf{vsrc}(G) \) within a factor \( n^{1-\varepsilon} \), unless P = NP.}, author = {Issac, Davis and van Leeuwen, Erik Jan and Das, Anita and Chandran, L. Sunil}, booktitle = {Latin American Symposium on Theoretical Informatics Conference (LATIN)}, keywords = {anitadas davisissac erikjanvanleeuwen latin lsunilchandran year2018}, title = {Algorithms and bounds for very strong rainbow coloring}, year = 2018 }
• 
  Issac, Davis; van Leeuwen, Erik Jan; Lauri, Juho; Lima, Paloma; Heggernes, PinarRainbow Vertex Coloring Bipartite Graphs and Chordal Graphs. Mathematical Foundations of Computer Science (MFCS) 2018
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.
  @inproceedings{illlh-rvcbgcg-2018, abstract = {Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.}, author = {Issac, Davis and van Leeuwen, Erik Jan and Lauri, Juho and Lima, Paloma and Heggernes, Pinar}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, keywords = {davisissac erikjanvanleeuwen juholauri mfcs palomalima pinarheggernes year2018}, title = {Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs}, year = 2018 }

2016 [ nach oben ]

• 
  Issac, Davis; Chandran, L. Sunil; Karrenbauer, AndreasOn the Parameterized Complexity of Biclique Cover and Partition. International Symposium on Parameterized and Exact Computation (IPEC) 2016
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Given a bipartite graph G, we consider the decision problem called Biclique Cover for a fixed positive integer parameter k where we are asked whether the edges of G can be covered with at most k complete bipartite subgraphs (a.k.a. bicliques). In the Biclique Partition problem, we have the additional constraint that each edge should appear in exactly one of the k bicliques. These problems are both known to be NP-complete but fixed parameter tractable. However, the known FPT algorithms have a running time that is doubly exponential in k, and the best known kernel for both problems is exponential in k. We build on this kernel and improve the running time for Biclique partition to \(2^{O(k^2) \) by exploiting a linear algebraic view on this problem. On the other hand, we show that no such improvement is possible for Biclique Cover unless the Exponential Time Hypothesis (ETH) is false by proving a doubly exponential lower bound on the running time. We achieve this by giving a reduction from 3SAT on n variables to an instance of Biclique Cover with \( k=O(\log n) \). As a further consequence of this reduction, we show that there is no subexponential kernel for Biclique Cover unless \( P=NP \). Finally, we point out the significance of the exponential kernel mentioned above for the design of polynomial-time approximation algorithms for the optimization versions of both problems. That is, we show that it is possible to obtain approximation factors of \( n/\log n\) for both problems, whereas the previous best approximation factor was \(n/\sqrt(\log n)\).
  @inproceedings{ick-opcbcp-2016, abstract = {Given a bipartite graph G, we consider the decision problem called Biclique Cover for a fixed positive integer parameter k where we are asked whether the edges of G can be covered with at most k complete bipartite subgraphs (a.k.a. bicliques). In the Biclique Partition problem, we have the additional constraint that each edge should appear in exactly one of the k bicliques. These problems are both known to be NP-complete but fixed parameter tractable. However, the known FPT algorithms have a running time that is doubly exponential in k, and the best known kernel for both problems is exponential in k. We build on this kernel and improve the running time for Biclique partition to \(2^{O(k^2)} \) by exploiting a linear algebraic view on this problem. On the other hand, we show that no such improvement is possible for Biclique Cover unless the Exponential Time Hypothesis (ETH) is false by proving a doubly exponential lower bound on the running time. We achieve this by giving a reduction from 3SAT on n variables to an instance of Biclique Cover with \( k=O(\log n) \). As a further consequence of this reduction, we show that there is no subexponential kernel for Biclique Cover unless \( P=NP \). Finally, we point out the significance of the exponential kernel mentioned above for the design of polynomial-time approximation algorithms for the optimization versions of both problems. That is, we show that it is possible to obtain approximation factors of \( n/\log n\) for both problems, whereas the previous best approximation factor was \(n/\sqrt(\log n)\).}, author = {Issac, Davis and Chandran, L. Sunil and Karrenbauer, Andreas}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, keywords = {andreaskarrenbauer davisissac ipec lsunilchandran year2016}, title = {On the Parameterized Complexity of Biclique Cover and Partition}, year = 2016 }