3 Search Results for "McConnell, Ross M."

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

DOI: 10.4230/LIPIcs.MFCS.2018.68

Interval-Like Graphs and Digraphs

Authors: Pavol Hell, Jing Huang, Ross M. McConnell, and Arash Rafiey

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

We unify several seemingly different graph and digraph classes under one umbrella. These classes are all, broadly speaking, different generalizations of interval graphs, and include, in addition to interval graphs, adjusted interval digraphs, threshold graphs, complements of threshold tolerance graphs (known as `co-TT' graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray graphs. (The last three classes coincide, but have been investigated in different contexts.) This common view is made possible by introducing reflexive relationships (loops) into the analysis. We also show that all the above classes are united by a common ordering characterization, the existence of a min ordering. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, and show that they are precisely the digraphs that are characterized by the existence of a min ordering. We also offer an alternative geometric characterization of these digraphs. For most of the above graph and digraph classes, we show that they are exactly those signed-interval digraphs that satisfy a suitable natural restriction on the digraph, like having a loop on every vertex, or having a symmetric edge-set, or being bipartite. For instance, co-TT graphs are precisely those signed-interval digraphs that have each edge symmetric. We also offer some discussion of future work on recognition algorithms and characterizations.

Cite as

Pavol Hell, Jing Huang, Ross M. McConnell, and Arash Rafiey. Interval-Like Graphs and Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 68:1-68:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hell_et_al:LIPIcs.MFCS.2018.68,
  author =	{Hell, Pavol and Huang, Jing and McConnell, Ross M. and Rafiey, Arash},
  title =	{{Interval-Like Graphs and Digraphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{68:1--68:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.68},
  URN =		{urn:nbn:de:0030-drops-96503},
  doi =		{10.4230/LIPIcs.MFCS.2018.68},
  annote =	{Keywords: graph theory, interval graphs, interval bigraphs, min ordering, co-TT graph}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2018.69

Double Threshold Digraphs

Authors: Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, and Zhisheng Xu

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

A semiorder is a model of preference relations where each element x is associated with a utility value alpha(x), and there is a threshold t such that y is preferred to x iff alpha(y) - alpha(x) > t. These are motivated by the notion that there is some uncertainty in the utility values we assign an object or that a subject may be unable to distinguish a preference between objects whose values are close. However, they fail to model the well-known phenomenon that preferences are not always transitive. Also, if we are uncertain of the utility values, it is not logical that preference is determined absolutely by a comparison of them with an exact threshold. We propose a new model in which there are two thresholds, t_1 and t_2; if the difference alpha(y) - alpha(x) is less than t_1, then y is not preferred to x; if the difference is greater than t_2 then y is preferred to x; if it is between t_1 and t_2, then y may or may not be preferred to x. We call such a relation a (t_1,t_2) double-threshold semiorder, and the corresponding directed graph G = (V,E) a (t_1,t_2) double-threshold digraph. Every directed acyclic graph is a double-threshold digraph; increasing bounds on t_2/t_1 give a nested hierarchy of subclasses of the directed acyclic graphs. In this paper we characterize the subclasses in terms of forbidden subgraphs, and give algorithms for finding an assignment of utility values that explains the relation in terms of a given (t_1,t_2) or else produces a forbidden subgraph, and finding the minimum value lambda of t_2/t_1 that is satisfiable for a given directed acyclic graph. We show that lambda gives a useful measure of the complexity of a directed acyclic graph with respect to several optimization problems that are NP-hard on arbitrary directed acyclic graphs.

Cite as

Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, and Zhisheng Xu. Double Threshold Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 69:1-69:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hamburger_et_al:LIPIcs.MFCS.2018.69,
  author =	{Hamburger, Peter and McConnell, Ross M. and P\'{o}r, Attila and Spinrad, Jeremy P. and Xu, Zhisheng},
  title =	{{Double Threshold Digraphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{69:1--69:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.69},
  URN =		{urn:nbn:de:0030-drops-96519},
  doi =		{10.4230/LIPIcs.MFCS.2018.69},
  annote =	{Keywords: posets, preference relations, approximation algorithms}
}

Refine by Author
2 McConnell, Ross M.
1 Coudert, David
1 Csikós, Mónika
1 Ducoffe, Guillaume
1 Hamburger, Peter
Show More...

Refine by Classification
1 Mathematics of computing → Combinatoric problems
1 Mathematics of computing → Graph algorithms
1 Mathematics of computing → Graph theory
1 Theory of computation → Algorithm design techniques
1 Theory of computation → Graph algorithms analysis
Show More...

Refine by Keyword
1 VC-dimension
1 algorithm
1 approximation algorithms
1 co-TT graph
1 graph
Show More...

Refine by Type
3 document

Refine by Publication Year
2 2018
1 2024