5 Search Results for "Sikdar, Somnath"

Document
DOI: 10.4230/LIPIcs.SEA.2024.8
Practical Computation of Graph VC-Dimension

Authors: David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
For any set system ℋ = (V,ℛ), ℛ ⊆ 2^V, a subset S ⊆ V is called shattered if every S' ⊆ S results from the intersection of S with some set in ℛ. The VC-dimension of ℋ is the size of a largest shattered set in V. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph G = (V,E), the VC-dimension of G is defined as the VC-dimension of (V, N), where N contains each subset of V that can be obtained as the closed neighborhood of some vertex v ∈ V in G. Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the W[1]-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.
Cite as

David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coudert_et_al:LIPIcs.SEA.2024.8,
  author =	{Coudert, David and Csik\'{o}s, M\'{o}nika and Ducoffe, Guillaume and Viennot, Laurent},
  title =	{{Practical Computation of Graph VC-Dimension}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8},
  URN =		{urn:nbn:de:0030-drops-203731},
  doi =		{10.4230/LIPIcs.SEA.2024.8},
  annote =	{Keywords: VC-dimension, graph, algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.33
Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations

Authors: Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
For a fixed graph H, the H-Subgraph Hitting problem consists in deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of H as a subgraph. This problem can be seen as a generalization of Vertex Cover, which corresponds to the case H = K₂. We initiate a study of H-Subgraph Hitting from the point of view of characterizing structural parameterizations that allow for polynomial kernels, within the recently active framework of taking as the parameter the number of vertex deletions to obtain a graph in a "simple" class 𝒞. Our main contribution is to identify graph parameters that, when H-Subgraph Hitting is parameterized by the vertex-deletion distance to a class 𝒞 where any of these parameters is bounded, and assuming standard complexity assumptions and that H is biconnected, allow us to prove the following sharp dichotomy: the problem admits a polynomial kernel if and only if H is a clique. These new graph parameters are inspired by the notion of 𝒞-elimination distance introduced by Bulian and Dawar [Algorithmica 2016], and generalize it in two directions. Our results also apply to the version of the problem where one wants to hit H as an induced subgraph, and imply in particular, that the problems of hitting minors and hitting (induced) subgraphs have a substantially different behavior with respect to the existence of polynomial kernels under structural parameterizations.
Cite as

Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bougeret_et_al:LIPIcs.ICALP.2024.33,
  author =	{Bougeret, Marin and Jansen, Bart M. P. and Sau, Ignasi},
  title =	{{Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.33},
  URN =		{urn:nbn:de:0030-drops-201766},
  doi =		{10.4230/LIPIcs.ICALP.2024.33},
  annote =	{Keywords: hitting subgraphs, hitting induced subgraphs, parameterized complexity, polynomial kernel, complexity dichotomy, elimination distance}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.31
Kernelization and Sparseness: the Case of Dominating Set

Authors: Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
We prove that for every positive integer r and for every graph class G of bounded expansion, the r-DOMINATING SET problem admits a linear kernel on graphs from G. Moreover, in the more general case when G is only assumed to be nowhere dense, we give an almost linear kernel on G for the classic DOMINATING SET problem, i.e., for the case r=1. These results generalize a line of previous research on finding linear kernels for DOMINATING SET and r-DOMINATING SET (Alber et al., JACM 2004, Bodlaender et al., FOCS 2009, Fomin et al., SODA 2010, Fomin et al., SODA 2012, Fomin et al., STACS 2013). However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related CONNECTED DOMINATING SET problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on H-topological-minor-free graphs (Fomin et al., STACS 2013). Also, we prove that for any somewhere dense class G, there is some r for which r-DOMINATING SET is W[2]-hard on G. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of r-DOMINATING SET on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.
Cite as

Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and Sparseness: the Case of Dominating Set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{drange_et_al:LIPIcs.STACS.2016.31,
  author =	{Drange, P\r{a}l Gr{\o}n\r{a}s and Dregi, Markus and Fomin, Fedor V. and Kreutzer, Stephan and Lokshtanov, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Reidl, Felix and S\'{a}nchez Villaamil, Fernando and Saurabh, Saket and Siebertz, Sebastian and Sikdar, Somnath},
  title =	{{Kernelization and Sparseness: the Case of Dominating Set}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.31},
  URN =		{urn:nbn:de:0030-drops-57327},
  doi =		{10.4230/LIPIcs.STACS.2016.31},
  annote =	{Keywords: kernelization, dominating set, bounded expansion, nowhere dense}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.402
Fast Biclustering by Dual Parameterization

Authors: Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, and Somnath Sikdar

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none of the problems can be solved in subexponential time unless the exponential time hypothesis fails. Misra, Panolan, and Saurabh (MFCS 2013) argue that introducing a bound on the number of connected components in the solution should not make the problem easier: In particular, they argue that the subexponential time algorithm for editing to a fixed number of clusters (p-Cluster Editing) by Fomin et al. (J. Comput. Syst. Sci., 80(7) 2014) is an exception rather than the rule. Here, p is a secondary parameter, bounding the number of components in the solution. However, upon bounding the number of stars or bicliques in the solution, we obtain algorithms which run in time O(2^{3*sqrt(pk)} + n + m) for p-Starforest Editing and O(2^{O(p * sqrt(k) * log(pk))} + n + m) for p-Bicluster Editing. We obtain a similar result for the more general case of t-Partite p-Cluster Editing. This is subexponential in k for a fixed number of clusters, since p is then considered a constant. Our results even out the number of multivariate subexponential time algorithms and give reasons to believe that this area warrants further study.
Cite as

Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, and Somnath Sikdar. Fast Biclustering by Dual Parameterization. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 402-413, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{drange_et_al:LIPIcs.IPEC.2015.402,
  author =	{Drange, P\r{a}l Gr{\o}n\r{a}s and Reidl, Felix and S\'{a}nchez Villaamil, Fernando and Sikdar, Somnath},
  title =	{{Fast Biclustering by Dual Parameterization}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{402--413},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.402},
  URN =		{urn:nbn:de:0030-drops-56004},
  doi =		{10.4230/LIPIcs.IPEC.2015.402},
  annote =	{Keywords: graph editing, subexponential algorithms, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.326
Lower Bounds on the Complexity of MSO_1 Model-Checking

Authors: Robert Ganian, Petr Hlineny, Alexander Langer, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar

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

Abstract
One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (MSO2) is decidable in linear time on any class of graphs of bounded tree-width. In the parlance of parameterized complexity, this means that MSO2 model-checking is fixed-parameter tractable with respect to the tree-width as parameter. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound---that MSO2 model-checking is not even in XP wrt the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result. We show that even MSO1 model-checking with a fixed set of vertex labels, but without edge-set quantifications, is not in XP wrt the formula size as parameter for graph classes which are subgraph-closed and whose tree-width is poly-logarithmically unbounded unless the non-uniform ETH fails. In comparison to Kreutzer and Tazari, (1) we use a stronger prerequisite, namely non-uniform instead of uniform ETH, to avoid the effectiveness assumption and the construction of certain obstructions used in their proofs; and (2) we assume a different set of problems to be efficiently decidable, namely MSO1-definable properties on vertex labeled graphs instead of MSO2-definable properties on unlabeled graphs. Our result has an interesting consequence in the realm of digraph width measures: Strengthening a recent result, we show that no subdigraph-monotone measure can be algorithmically useful, unless it is within a poly-logarithmic factor of (undirected) tree-width.
Cite as

Robert Ganian, Petr Hlineny, Alexander Langer, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar. Lower Bounds on the Complexity of MSO_1 Model-Checking. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 326-337, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.STACS.2012.326,
  author =	{Ganian, Robert and Hlineny, Petr and Langer, Alexander and Obdr\v{z}\'{a}lek, Jan and Rossmanith, Peter and Sikdar, Somnath},
  title =	{{Lower Bounds on the Complexity of MSO\underline1 Model-Checking}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{326--337},
  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.326},
  URN =		{urn:nbn:de:0030-drops-34185},
  doi =		{10.4230/LIPIcs.STACS.2012.326},
  annote =	{Keywords: Monadic Second-Order Logic, Treewidth, Lower Bounds, Exponential Time Hypothesis, Parameterized Complexity}
}
  • Refine by Author
  • 3 Sikdar, Somnath
  • 2 Drange, Pål Grønås
  • 2 Reidl, Felix
  • 2 Sánchez Villaamil, Fernando
  • 1 Bougeret, Marin
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Algorithm design techniques

  • Refine by Keyword
  • 2 parameterized complexity
  • 1 Exponential Time Hypothesis
  • 1 Lower Bounds
  • 1 Monadic Second-Order Logic
  • 1 Parameterized Complexity
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2024
  • 1 2012
  • 1 2015
  • 1 2016

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact