2026-07-25T11:56:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9056 2024-03-06T10:43:15Z ddc:004 open_access

A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error Fichtenberger, Hendrik Levi, Reut Vasudev, Yadu Wötzel, Maximilian graph property testing minor-free graphs We consider one-sided error property testing of F-minor freeness in bounded-degree graphs for any finite family of graphs F that contains a minor of K_{2,k}, the k-circus graph, or the (k x 2)-grid for any k in N. This includes, for instance, testing whether a graph is outerplanar or a cactus graph. The query complexity of our algorithm in terms of the number of vertices in the graph, n, is O~(n^{2/3} / epsilon^5). Czumaj et al. (2014) showed that cycle-freeness and C_k-minor freeness can be tested with query complexity O~(sqrt{n}) by using random walks, and that testing H-minor freeness for any H that contains a cycles requires Omega(sqrt{n}) queries. In contrast to these results, we analyze the structure of the graph and show that either we can find a subgraph of sublinear size that includes the forbidden minor H, or we can find a pair of disjoint subsets of vertices whose edge-cut is large, which induces an H-minor. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hendrik Fichtenberger and Reut Levi and Yadu Vasudev and Maximilian Wötzel 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.52 urn:nbn:de:0030-drops-90563 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.52 eng https://creativecommons.org/licenses/by/3.0/legalcode