Geodesic
Quasipolynomiality of the Smallest Missing Induced Subgraph
Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 5, pp. 329-339.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We study the problem of finding the smallest graph that does not occur as an induced subgraph of a given graph. This missing induced subgraph has at most logarithmic size and can be found by a brute-force search, in an $n$-vertex graph, in time $n^{O(\log n)}$. We show that under the Exponential Time Hypothesis this quasipolynomial time bound is optimal. We also consider variations of the problem in which either the missing subgraph or the given graph comes from a restricted graph family; for instance, we prove that the smallest missing planar induced subgraph of a given planar graph can be found in polynomial time.
DOI : 10.7155/jgaa.00625
Keywords: Quasipolynomial time, Induced subgraph isomorphism, Smallest missing subgraph, Exponential time hypothesis 
@article{JGAA_2023_27_5_a0,
     author = {David Eppstein and Andrea Lincoln and Virginia Vassilevska Williams},
     title = {Quasipolynomiality of the {Smallest} {Missing} {Induced} {Subgraph}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {329--339},
     publisher = {mathdoc},
     volume = {27},
     number = {5},
     year = {2023},
     doi = {10.7155/jgaa.00625},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00625/}
}
TY  - JOUR
AU  - David Eppstein
AU  - Andrea Lincoln
AU  - Virginia Vassilevska Williams
TI  - Quasipolynomiality of the Smallest Missing Induced Subgraph
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 329
EP  - 339
VL  - 27
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00625/
DO  - 10.7155/jgaa.00625
LA  - en
ID  - JGAA_2023_27_5_a0
ER  - 
%0 Journal Article
%A David Eppstein
%A Andrea Lincoln
%A Virginia Vassilevska Williams
%T Quasipolynomiality of the Smallest Missing Induced Subgraph
%J Journal of Graph Algorithms and Applications
%D 2023
%P 329-339
%V 27
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00625/
%R 10.7155/jgaa.00625
%G en
%F JGAA_2023_27_5_a0
David Eppstein; Andrea Lincoln; Virginia Vassilevska Williams. Quasipolynomiality of the Smallest Missing Induced Subgraph. Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 5, pp. 329-339. doi : 10.7155/jgaa.00625. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00625/

Cité par Sources :