Search Results

Documents authored by Narayanaswamy, N. S.

Found 2 Possible Name Variants:

Narayanaswamy, N.S.

Document
DOI: 10.4230/LIPIcs.STACS.2012.338
LP can be a cure for Parameterized Problems

Authors: N.S. Narayanaswamy, Venkatesh Raman, M.S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We investigate the parameterized complexity of Vertex Cover parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O^*(2.6181^r) algorithm for the problem where r is the excess of the vertex cover size over the LP optimum. We write O^*(f(k)) for a time complexity of the form O(f(k)n^{O(1)}), where f(k) grows exponentially with k. Then, using known and new reductions, we give O^*(2.6181^k) algorithms for the parameterized versions of Above Guarantee Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion and Almost 2-SAT, and an O^*(1.6181^k) algorithm for Konig Vertex Deletion, Vertex Cover Param by OCT and Vertex Cover Param by KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for Odd Cycle Transversal for which this is the first major improvement after the first algorithm that showed it fixed-parameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2k-O(log k) vertices.
Cite as

N.S. Narayanaswamy, Venkatesh Raman, M.S. Ramanujan, and Saket Saurabh. LP can be a cure for Parameterized Problems. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 338-349, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{narayanaswamy_et_al:LIPIcs.STACS.2012.338,
  author =	{Narayanaswamy, N.S. and Raman, Venkatesh and Ramanujan, M.S. and Saurabh, Saket},
  title =	{{LP can be a cure for Parameterized Problems}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{338--349},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.338},
  URN =		{urn:nbn:de:0030-drops-34291},
  doi =		{10.4230/LIPIcs.STACS.2012.338},
  annote =	{Keywords: Algorithms and data structures. Graph Algorithms, Parameterized Algorithms.}
}

Narayanaswamy, N. S.

Document
DOI: 10.4230/LIPIcs.SWAT.2024.4
Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage

Authors: Girish Balakrishnan, Sankardeep Chakraborty, N. S. Narayanaswamy, and Kunihiko Sadakane

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
Chordal graphs is a well-studied large graph class that is also a strict super-class of path graphs. Munro and Wu (ISAAC 2018) have given an (n²/4+o(n²))-bit succinct representation for n-vertex unlabeled chordal graphs. A chordal graph G = (V,E) is the intersection graph of sub-trees of a tree T. Based on this characterization, the two parameters of chordal graphs which we consider in this work are leafage, introduced by Lin, McKee and West (Discussiones Mathematicae Graph Theory 1998) and vertex leafage, introduced by Chaplick and Stacho (Discret. Appl. Math. 2014). Leafage is the minimum number of leaves in any possible tree T characterizing G. Let L(u) denote the number of leaves of the sub-tree in T corresponding to u ∈ V and k = max_{u ∈ V} L(u). The smallest k for which there exists a tree T for G is called its vertex leafage. In this work, we improve the worst-case information theoretic lower bound of Munro and Wu (ISAAC 2018) for n-vertex unlabeled chordal graphs when vertex leafage is bounded and leafage is unbounded. The class of unlabeled k-vertex leafage chordal graphs that consists of all chordal graphs with vertex leafage at most k and unbounded leafage, denoted 𝒢_k, is introduced for the first time. For k > 0 in o(n^c), c > 0, we obtain a lower bound of ((k-1)n log n -kn log k - O(log n))-bits on the size of any data structure that encodes a graph in 𝒢_k. Further, for every k-vertex leafage chordal graph G and k > 1 in o(n^c), c > 0, we present a ((k-1)n log n + o(kn log n))-bit succinct data structure, constructed using the succinct data structure for path graphs with (k-1)n vertices. Our data structure supports adjacency query in O(k log n) time and using additional 2n log n bits, an O(k² d_v log n + log² n) time neighbourhood query where d_v is degree of v ∈ V.
Cite as

Girish Balakrishnan, Sankardeep Chakraborty, N. S. Narayanaswamy, and Kunihiko Sadakane. Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balakrishnan_et_al:LIPIcs.SWAT.2024.4,
  author =	{Balakrishnan, Girish and Chakraborty, Sankardeep and Narayanaswamy, N. S. and Sadakane, Kunihiko},
  title =	{{Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.4},
  URN =		{urn:nbn:de:0030-drops-200446},
  doi =		{10.4230/LIPIcs.SWAT.2024.4},
  annote =	{Keywords: succinct data structure, chordal graphs, leafage, vertex leafage, path graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.40
A Faster Algorithm for Vertex Cover Parameterized by Solution Size

Authors: David G. Harris and N. S. Narayanaswamy

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
We describe a new algorithm for vertex cover with runtime O^*(1.25284^k), where k is the size of the desired solution and O^* hides polynomial factors in the input size. This improves over the previous runtime of O^*(1.2738^k) due to Chen, Kanj, & Xia (2010) standing for more than a decade. The key to our algorithm is to use a measure which simultaneously tracks k as well as the optimal value λ of the vertex cover LP relaxation. This allows us to make use of prior algorithms for Maximum Independent Set in bounded-degree graphs and Above-Guarantee Vertex Cover. The main step in the algorithm is to branch on high-degree vertices, while ensuring that both k and μ = k - λ are decreased at each step. There can be local obstructions in the graph that prevent μ from decreasing in this process; we develop a number of novel branching steps to handle these situations.
Cite as

David G. Harris and N. S. Narayanaswamy. A Faster Algorithm for Vertex Cover Parameterized by Solution Size. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.STACS.2024.40,
  author =	{Harris, David G. and Narayanaswamy, N. S.},
  title =	{{A Faster Algorithm for Vertex Cover Parameterized by Solution Size}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.40},
  URN =		{urn:nbn:de:0030-drops-197508},
  doi =		{10.4230/LIPIcs.STACS.2024.40},
  annote =	{Keywords: Vertex cover, FPT, Graph algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.32
Budgeted Dominating Sets in Uncertain Graphs

Authors: Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, and R. Vijayaragunathan

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph 𝒢 = (V, E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1) We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is 𝖶[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in n^o(k) time. 2) We show that if one is willing to settle for (1-ε) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3) We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is 𝖶[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4) Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset Σ-Π Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.
Cite as

Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, and R. Vijayaragunathan. Budgeted Dominating Sets in Uncertain Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.MFCS.2021.32,
  author =	{Choudhary, Keerti and Cohen, Avi and Narayanaswamy, N. S. and Peleg, David and Vijayaragunathan, R.},
  title =	{{Budgeted Dominating Sets in Uncertain Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.32},
  URN =		{urn:nbn:de:0030-drops-144723},
  doi =		{10.4230/LIPIcs.MFCS.2021.32},
  annote =	{Keywords: Uncertain graphs, Dominating set, NP-hard, PTAS, treewidth, planar graph}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.52
Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs

Authors: S. M. Dhannya and N. S. Narayanaswamy

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Given a hypergraph H, the conflict-free colouring problem is to colour vertices of H using minimum colours so that in every hyperedge e of H, there is a vertex whose colour is different from that of all other vertices in e. Our results are on a variant of the conflict-free colouring problem considered by Cheilaris et al.[Cheilaris et al., 2014], known as the 1-Strong Conflict-Free (1-SCF) colouring problem, for which they presented a polynomial time 2-approximation algorithm for interval hypergraphs. We show that an optimum 1-SCF colouring for interval hypergraphs can be computed in polynomial time. Our results are obtained by considering a different view of conflict-free colouring which we believe could be useful in general. For interval hypergraphs, this different view brings a connection to the theory of perfect graphs which is useful in coming up with an LP formulation to select the vertices that could be coloured to obtain an optimum conflict-free colouring. The perfect graph connection again plays a crucial role in finding a minimum colouring for the vertices selected by the LP formulation.
Cite as

S. M. Dhannya and N. S. Narayanaswamy. Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dhannya_et_al:LIPIcs.STACS.2020.52,
  author =	{Dhannya, S. M. and Narayanaswamy, N. S.},
  title =	{{Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.52},
  URN =		{urn:nbn:de:0030-drops-119138},
  doi =		{10.4230/LIPIcs.STACS.2020.52},
  annote =	{Keywords: Conflict-free Colouring, Interval Hypergraphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.41
On the Complexity Landscape of Connected f-Factor Problems

Authors: Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak, C. S. Rahul, and M. S. Ramanujan

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Given an n-vertex graph G and a function f:V(G) -> {0, ..., n-1}, an f-factor is a subgraph H of G such that deg_H(v)=f(v) for every vertex v in V(G); we say that H is a connected f-factor if, in addition, the subgraph H is connected. A classical result of Tutte (1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connected f-factor is easily seen to generalize Hamiltonian Cycle and hence is NP-complete. In fact, the Connected f-Factor problem remains NP-complete even when f(v) is at least n^epsilon for each vertex v and epsilon<1; on the other side of the spectrum, the problem was known to be polynomial-time solvable when f(v) is at least n/3 for every vertex v. In this paper, we extend this line of work and obtain new complexity results based on restricting the function f. In particular, we show that when f(v) is required to be at least n/(log n)^c, the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c <= 1. We also show that when c>1, the problem is NP-intermediate.
Cite as

Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak, C. S. Rahul, and M. S. Ramanujan. On the Complexity Landscape of Connected f-Factor Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.MFCS.2016.41,
  author =	{Ganian, Robert and Narayanaswamy, N. S. and Ordyniak, Sebastian and Rahul, C. S. and Ramanujan, M. S.},
  title =	{{On the Complexity Landscape of  Connected f-Factor Problems}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.41},
  URN =		{urn:nbn:de:0030-drops-65013},
  doi =		{10.4230/LIPIcs.MFCS.2016.41},
  annote =	{Keywords: f-factors, connected f-factors, quasi-polynomial time algorithms, randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.23
Hitting Set for Hypergraphs of Low VC-dimension

Authors: Karl Bringmann, László Kozma, Shay Moran, and N. S. Narayanaswamy

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We study the complexity of the Hitting Set problem in set systems (hypergraphs) that avoid certain sub-structures. In particular, we characterize the classical and parameterized complexity of the problem when the Vapnik-Chervonenkis dimension (VC-dimension) of the input is small. VC-dimension is a natural measure of complexity of set systems. Several tractable instances of Hitting Set with a geometric or graph-theoretical flavor are known to have low VC-dimension. In set systems of bounded VC-dimension, Hitting Set is known to admit efficient and almost optimal approximation algorithms (Brönnimann and Goodrich, 1995; Even, Rawitz, and Shahar, 2005; Agarwal and Pan, 2014). In contrast to these approximation-results, a low VC-dimension does not necessarily imply tractability in the parameterized sense. In fact, we show that Hitting Set is W[1]-hard already on inputs with VC-dimension 2, even if the VC-dimension of the dual set system is also 2. Thus, Hitting Set is very unlikely to be fixed-parameter tractable even in this arguably simple case. This answers an open question raised by King in 2010. For set systems whose (primal or dual) VC-dimension is 1, we show that Hitting Set is solvable in polynomial time. To bridge the gap in complexity between the classes of inputs with VC-dimension 1 and 2, we use a measure that is more fine-grained than VC-dimension. In terms of this measure, we identify a sharp threshold where the complexity of Hitting Set transitions from polynomial-time-solvable to NP-hard. The tractable class that lies just under the threshold is a generalization of Edge Cover, and thus extends the domain of polynomial-time tractability of Hitting Set.
Cite as

Karl Bringmann, László Kozma, Shay Moran, and N. S. Narayanaswamy. Hitting Set for Hypergraphs of Low VC-dimension. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ESA.2016.23,
  author =	{Bringmann, Karl and Kozma, L\'{a}szl\'{o} and Moran, Shay and Narayanaswamy, N. S.},
  title =	{{Hitting Set for Hypergraphs of Low VC-dimension}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.23},
  URN =		{urn:nbn:de:0030-drops-63749},
  doi =		{10.4230/LIPIcs.ESA.2016.23},
  annote =	{Keywords: hitting set, VC-dimension}
}
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