2 Search Results for "Rajendraprasad, Deepak"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.5
Packing Arc-Disjoint 4-Cycles in Oriented Graphs

Authors: Jasine Babu, R. Krithika, and Deepak Rajendraprasad

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Given a directed graph G and a positive integer k, the Arc Disjoint r-Cycle Packing problem asks whether G has k arc-disjoint r-cycles. We show that, for each integer r ≥ 3, Arc Disjoint r-Cycle Packing is NP-complete on oriented graphs with girth r. When r is even, the same result holds even when the input class is further restricted to be bipartite. On the positive side, focusing on r = 4 in oriented graphs, we study the complexity of the problem with respect to two parameterizations: solution size and vertex cover size. For the former, we give a cubic kernel with quadratic number of vertices. This is smaller than the compression size guaranteed by a reduction to the well-known 4-Set Packing. For the latter, we show fixed-parameter tractability using an unapparent integer linear programming formulation of an equivalent problem.
Cite as

Jasine Babu, R. Krithika, and Deepak Rajendraprasad. Packing Arc-Disjoint 4-Cycles in Oriented Graphs. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{babu_et_al:LIPIcs.FSTTCS.2022.5,
  author =	{Babu, Jasine and Krithika, R. and Rajendraprasad, Deepak},
  title =	{{Packing Arc-Disjoint 4-Cycles in Oriented Graphs}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.5},
  URN =		{urn:nbn:de:0030-drops-173979},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.5},
  annote =	{Keywords: arc-disjoint cycles, bipartite digraphs, oriented graphs, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.153
Inapproximability of Rainbow Colouring

Authors: L. Sunil Chandran and Deepak Rajendraprasad

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one path in which no two edges are coloured the same. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Chakraborty, Fischer, Matsliah and Yuster have shown that it is NP-hard to compute the rainbow connection number of graphs [J. Comb. Optim., 2011]. Basavaraju, Chandran, Rajendraprasad and Ramaswamy have reported an (r+3)-factor approximation algorithm to rainbow colour any graph of radius r [Graphs and Combinatorics, 2012]. In this article, we use a result of Guruswami, Håstad and Sudan on the NP-hardness of colouring a 2-colourable 4-uniform hypergraph using constantly many colours [SIAM J. Comput., 2002] to show that for every positive integer k, it is NP-hard to distinguish between graphs with rainbow connection number 2k+2 and 4k+2. This, in turn, implies that there cannot exist a polynomial time algorithm to rainbow colour graphs with less than twice the optimum number of colours, unless P=NP. The authors have earlier shown that the rainbow connection number problem remains NP-hard even when restricted to the class of chordal graphs, though in this case a 4-factor approximation algorithm is available [COCOON, 2012]. In this article, we improve upon the 4-factor approximation algorithm to design a linear-time algorithm that can rainbow colour a chordal graph G using at most 3/2 times the minimum number of colours if G is bridgeless and at most 5/2 times the minimum number of colours otherwise. Finally we show that the rainbow connection number of bridgeless chordal graphs cannot be polynomial-time approximated to a factor less than 5/4, unless P=NP.
Cite as

L. Sunil Chandran and Deepak Rajendraprasad. Inapproximability of Rainbow Colouring. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 153-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chandran_et_al:LIPIcs.FSTTCS.2013.153,
  author =	{Chandran, L. Sunil and Rajendraprasad, Deepak},
  title =	{{Inapproximability of Rainbow Colouring}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{153--162},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.153},
  URN =		{urn:nbn:de:0030-drops-43689},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.153},
  annote =	{Keywords: rainbow connectivity, rainbow colouring, approximation hardness}
}
  • Refine by Author
  • 2 Rajendraprasad, Deepak
  • 1 Babu, Jasine
  • 1 Chandran, L. Sunil
  • 1 Krithika, R.

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 approximation hardness
  • 1 arc-disjoint cycles
  • 1 bipartite digraphs
  • 1 oriented graphs
  • 1 parameterized complexity
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2013
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact