Search Results

Documents authored by Csikós, Mónika

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.49
An Optimal Sparsification Lemma for Low-Crossing Matchings and Its Applications to Discrepancy and Approximations

Authors: Mónika Csikós and Nabil H. Mustafa

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

Abstract
Matchings with low crossing numbers were originally introduced in the late 1980s in the seminal works of Welzl [Welzl, 1988; Welzl, 1992] and Chazelle-Welzl [Chazelle and Welzl, 1989]. They have since become fundamental structures in combinatorics, computational geometry, and algorithms. In this paper, we study matchings with low crossing numbers and their relation to random samples. In particular, our main technical result states that, given a set system (X, 𝒮) with dual VC-dimension d and a parameter α ∈ (0, 1], a random set of Θ̃(n^{1+α}) edges of binom(X,2) contains a linear-sized matching with crossing number O (n^{1-α/d}). Furthermore, we show that this bound is optimal up to a logarithmic factor. By incorporating the above sampling step to existing algorithms, we obtain improved running times, by a factor of Θ̃(n), for computing matchings with low crossing numbers. This immediately implies new bounds for a number of well-studied problems, such as combinatorial discrepancy, ε-approximations and their applications. To the best of our knowledge, these are the first near-linear time algorithms for general, non-geometric set systems, for a) matchings with sub-linear crossing numbers, and b) discrepancy beating the standard deviation bound. As an immediate consequence we get fast algorithms for computing o(1/ε²)-sized ε-approximations.
Cite as

Mónika Csikós and Nabil H. Mustafa. An Optimal Sparsification Lemma for Low-Crossing Matchings and Its Applications to Discrepancy and Approximations. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{csikos_et_al:LIPIcs.ICALP.2024.49,
  author =	{Csik\'{o}s, M\'{o}nika and Mustafa, Nabil H.},
  title =	{{An Optimal Sparsification Lemma for Low-Crossing Matchings and Its Applications to Discrepancy and Approximations}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{49:1--49:18},
  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.49},
  URN =		{urn:nbn:de:0030-drops-201925},
  doi =		{10.4230/LIPIcs.ICALP.2024.49},
  annote =	{Keywords: low-crossing matchings, uniform sampling, discrepancy, approximations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.28
Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications

Authors: Mónika Csikós and Nabil H. Mustafa

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Given a set system (X, S), constructing a matching of X with low crossing number is a key tool in combinatorics and algorithms. In this paper we present a new sampling-based algorithm which is applicable to finite set systems. Let n = |X|, m = | S| and assume that X has a perfect matching M such that any set in 𝒮 crosses at most κ = Θ(n^γ) edges of M. In the case γ = 1- 1/d, our algorithm computes a perfect matching of X with expected crossing number at most 10 κ, in expected time Õ (n^{2+(2/d)} + mn^(2/d)). As an immediate consequence, we get improved bounds for constructing low-crossing matchings for a slew of both abstract and geometric problems, including many basic geometric set systems (e.g., balls in ℝ^d). This further implies improved algorithms for many well-studied problems such as construction of ε-approximations. Our work is related to two earlier themes: the work of Varadarajan (STOC '10) / Chan et al. (SODA '12) that avoids spatial partitionings for constructing ε-nets, and of Chan (DCG '12) that gives an optimal algorithm for matchings with respect to hyperplanes in ℝ^d. Another major advantage of our method is its simplicity. An implementation of a variant of our algorithm in C++ is available on Github; it is approximately 200 lines of basic code without any non-trivial data-structure. Since the start of the study of matchings with low-crossing numbers with respect to half-spaces in the 1980s, this is the first implementation made possible for dimensions larger than 2.
Cite as

Mónika Csikós and Nabil H. Mustafa. Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{csikos_et_al:LIPIcs.SoCG.2021.28,
  author =	{Csik\'{o}s, M\'{o}nika and Mustafa, Nabil H.},
  title =	{{Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.28},
  URN =		{urn:nbn:de:0030-drops-138273},
  doi =		{10.4230/LIPIcs.SoCG.2021.28},
  annote =	{Keywords: Matchings, crossing numbers, approximations}
}
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