Quasipolynomiality of the Smallest Missing Induced Subgraph
From MaRDI portal
Publication:6051910
DOI10.7155/jgaa.00625zbMath1522.05313arXiv2306.11185OpenAlexW4384303789MaRDI QIDQ6051910
Andrea Lincoln, Virginia Vassilevska Williams, David Eppstein
Publication date: 20 September 2023
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2306.11185
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- Extended dynamic subgraph statistics using \(h\)-index parameterized data structures
- Asymptotically optimal induced universal graphs
- Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
- Results on learnability and the Vapnik-Chervonenkis dimension
- Strong computational lower bounds via parameterized complexity
- Flips in planar graphs
- Asymptotic bounds for permutations containing many different patterns
- On finding a minimum dominating set in a tournament
- On limited nondeterminism and the complexity of the V-C dimension
- Lower bounds for superpatterns and universal sequences
- A census of simple planar triangulations
- Tight lower bounds for certain parameterized NP-hard problems
- Finding, Minimizing, and Counting Weighted Subgraphs
- Counting and Detecting Small Subgraphs via Equations
- Asymptotic enumeration and limit laws of planar graphs
- Planar Subgraph Isomorphism Revisited
- The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
- A Census of Planar Triangulations
- Universal graphs and induced-universal graphs
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Adjacency Labeling Schemes and Induced-Universal Graphs
- Optimal induced universal graphs for bounded-degree graphs
- The Parameterized Complexity of the k -Biclique Problem
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
- Homomorphisms are a good basis for counting small subgraphs
- Adjacency Labelling for Planar Graphs (and Beyond)
- Containing All Permutations
- Hyperbolic intersection graphs and (quasi)-polynomial time
- Canonical form for graphs in quasipolynomial time: preliminary report
- Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
- Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
