2026-10-05T13:47:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23400 2025-10-02T10:54:08Z ddc:004 open_access

On the Instance Optimality of Detecting Collisions and Subgraphs Ben-Eliezer, Omri Grossman, Tomer Naor, Moni instance optimality instance complexity unlabeled certificate subgraph detection collision detection Suppose you are given a function f: [n] → [n] via (black-box) query access to the function. You are looking to find something local, like a collision (a pair x ≠ y s.t. f(x) = f(y)). The question is whether knowing the "shape" of the function helps you or not (by shape we mean that some permutation of the function is known). Formally, we investigate the unlabeled instance optimality of substructure detection problems in graphs and functions. A problem is g(n)-instance optimal if it admits an algorithm A satisfying that for any possible input, the (randomized) query complexity of A is at most g(n) times larger than the query complexity of any algorithm A' which solves the same problem while holding an unlabeled copy of the input (i.e., any A' that "knows the structure of the input"). Our results point to a trichotomy of unlabeled instance optimality among substructure detection problems in graphs and functions: - A few very simple properties have an O(1)-instance optimal algorithm. - Most properties of graphs and functions, with examples such as containing a fixed point or a 3-collision in functions, or a triangle in graphs, are n^{c}-far from instance optimal for some constant c > 0. - The problems of collision detection in functions and finding a claw in a graph serve as a middle ground between the two regimes. We show that these two properties are not Ω(log n)-instance optimal, and conjecture that this bound is tight. We provide evidence towards this conjecture, by proving that finding a claw in a graph is O(log(n))-instance optimal among all input graphs for which the query complexity of an algorithm holding an unlabeled certificate is O(√{n/(log n)}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Omri Ben-Eliezer and Tomer Grossman and Moni Naor 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.23 urn:nbn:de:0030-drops-234002 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.23 eng https://creativecommons.org/licenses/by/4.0/legalcode