VC Density of Set Systems Definable in Tree-Like Graphs

Authors Adam Paszke, Michał Pilipczuk



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.78.pdf
  • Filesize: 0.75 MB
  • 13 pages

Document Identifiers

Author Details

Adam Paszke
  • University of Warsaw, Poland
Michał Pilipczuk
  • University of Warsaw, Poland

Cite AsGet BibTex

Adam Paszke and Michał Pilipczuk. VC Density of Set Systems Definable in Tree-Like Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 78:1-78:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.78

Abstract

We study set systems definable in graphs using variants of logic with different expressive power. Our focus is on the notion of Vapnik-Chervonenkis density: the smallest possible degree of a polynomial bounding the cardinalities of restrictions of such set systems. On one hand, we prove that if phi(x,y) is a fixed CMSO_1 formula and C is a class of graphs with uniformly bounded cliquewidth, then the set systems defined by phi in graphs from C have VC density at most |y|, which is the smallest bound that one could expect. We also show an analogous statement for the case when phi(x,y) is a CMSO_2 formula and C is a class of graphs with uniformly bounded treewidth. We complement these results by showing that if C has unbounded cliquewidth (respectively, treewidth), then, under some mild technical assumptions on C, the set systems definable by CMSO_1 (respectively, CMSO_2) formulas in graphs from C may have unbounded VC dimension, hence also unbounded VC density.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
Keywords
  • treewidth
  • cliquewidth
  • definable sets
  • Vapnik-Chervonenkis density

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pages 1576-1585, 2012. URL: https://doi.org/10.5555/2095116.2095241.
  2. Bruno Courcelle. Monadic second-order definable graph transductions: A survey. Theor. Comput. Sci., 126(1):53-75, 1994. URL: https://doi.org/10.1016/0304-3975(94)90268-2.
  3. Bruno Courcelle. Fly-automata for checking MSO₂ graph properties. Discret. Appl. Math., 245:236-252, 2018. URL: https://doi.org/10.1016/j.dam.2016.10.018.
  4. Bruno Courcelle. From tree-decompositions to clique-width terms. Discret. Appl. Math., 248:125-144, 2018. URL: https://doi.org/10.1016/j.dam.2017.04.040.
  5. Bruno Courcelle and Joost Engelfriet. A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars. Mathematical Systems Theory, 28(6):515-552, 1995. Google Scholar
  6. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discret. Appl. Math., 101(1-3):77-114, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00184-5.
  7. Bruno Courcelle and Sang-il Oum. Vertex-minors, monadic second-order logic, and a conjecture by Seese. J. Comb. Theory, Ser. B, 97(1):91-126, 2007. URL: https://doi.org/10.1016/j.jctb.2006.04.003.
  8. Joost Engelfriet and Vincent van Oostrom. Logical description of contex-free graph languages. J. Comput. Syst. Sci., 55(3):489-503, 1997. URL: https://doi.org/10.1006/jcss.1997.1510.
  9. Martin Grohe and György Turán. Learnability and definability in trees and similar structures. Theory Comput. Syst., 37(1):193-220, 2004. URL: https://doi.org/10.1007/s00224-003-1112-8.
  10. Nabil H. Mustafa and Kasturi R. Varadarajan. Epsilon-approximations and epsilon-nets. CoRR, abs/1702.03676, 2017. URL: http://arxiv.org/abs/1702.03676.
  11. Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. On the number of types in sparse graphs. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, pages 799-808, 2018. URL: https://doi.org/10.1145/3209108.3209178.
  12. Michael O Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141:1-35, 1969. Google Scholar
  13. Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. J. Comb. Theory, Ser. B, 41(1):92-114, 1986. URL: https://doi.org/10.1016/0095-8956(86)90030-4.
  14. Norbert Sauer. On the density of families of sets. J. Comb. Theory, Ser. A, 13(1):145-147, 1972. URL: https://doi.org/10.1016/0097-3165(72)90019-2.
  15. Detlef Seese. The structure of models of decidable monadic theories of graphs. Ann. Pure Appl. Logic, 53(2):169-195, 1991. URL: https://doi.org/10.1016/0168-0072(91)90054-P.
  16. Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247-261, 1972. Google Scholar
  17. Vladimir Vapnik and Alexei Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Soviet Mathematics Doklady, 1971. Google Scholar
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