2019 [ to top ]

• 
  Issac, Davis; Chandran, L. Sunil; Zhou, Sanming Hadwiger's conjecture for squares of 2-trees. European Journal of Combinatorics 2019
  [ BibTeX ] [ Download ]
   
  @article{noauthororeditor, author = {Issac, Davis and Chandran, L. Sunil and Zhou, Sanming}, journal = {European Journal of Combinatorics}, keywords = {davisissac ejc lsunilchandran sanmingzhou year2019}, title = {Hadwiger's conjecture for squares of 2-trees}, volume = 76, year = 2019 }

2018 [ to top ]

• 
  Issac, Davis; Bhattacharya, Anup; Kumar, Amit; Jaiswal, Ragesh Sampling in space restricted settings. Algorithmica 2018: 1439-1458
  [ BibTeX ] [ URL ] [ Download ]
   
  @article{noauthororeditor, author = {Issac, Davis and Bhattacharya, Anup and Kumar, Amit and Jaiswal, Ragesh}, journal = {Algorithmica}, keywords = {algorithmica amitkumar anupbhattacharya davisissac rageshjaiswal year2018}, month = {June}, pages = {1439-1458}, title = {Sampling in space restricted settings}, volume = 80, year = 2018 }
• 
  Issac, Davis; van Leeuwen, Erik Jan; Lauri, Juho; Lima, Paloma; Heggernes, Pinar Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs. Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science 2018
  [ BibTeX ] [ Download ]
   
  @inproceedings{noauthororeditor, author = {Issac, Davis and van Leeuwen, Erik Jan and Lauri, Juho and Lima, Paloma and Heggernes, Pinar}, booktitle = {Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science}, keywords = {davisissac erikjanvanleeuwen juholauri mfcs palomalima pinarheggernes year2018}, title = {Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs}, year = 2018 }
• 
  Issac, Davis; Chandran, L. Sunil; Cheung, Yuen Kueng Spanning tree congestion and computation of gyori lovasz partition. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming 2018
  [ BibTeX ] [ URL ] [ Download ]
   
  @inproceedings{noauthororeditor, author = {Issac, Davis and Chandran, L. Sunil and Cheung, Yuen Kueng}, booktitle = {Proceedings of the 45th International Colloquium on Automata, Languages, and Programming}, 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. Sunil Algorithms and bounds for very strong rainbow coloring. Proceedings of the Latin American Symposium on Theoretical Informatics 2018 2018
  [ BibTeX ] [ Download ]
   
  @inproceedings{noauthororeditor, author = {Issac, Davis and van Leeuwen, Erik Jan and Das, Anita and Chandran, L. Sunil}, booktitle = {Proceedings of the Latin American Symposium on Theoretical Informatics 2018}, keywords = {anitadas davisissac erikjanvanleeuwen latin lsunilchandran year2018}, title = {Algorithms and bounds for very strong rainbow coloring}, year = 2018 }

2016 [ to top ]

• 
  Issac, Davis; Chandran, L. Sunil; Karrenbauer, Andreas On the Parameterized Complexity of Biclique Cover and Partition. Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) 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{noauthororeditor, 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 = {Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, keywords = {andreaskarrenbauer davisissac ipec lsunilchandran year2016}, title = {On the Parameterized Complexity of Biclique Cover and Partition}, year = 2016 }