{"ID":2835033,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.01121","arxiv_id":"2512.01121","title":"A practical algorithm for 3-admissibility","abstract":"The $3$-admissibility of a graph is a promising measure to identify real-world networks that have an algorithmically favourable structure. We design an algorithm that decides whether the $3$-admissibility of an input graph~$G$ is at most~$p$ in time~\\runtime and space~\\memory, where $m$ is the number of edges in $G$ and $n$ the number of vertices. To the best of our knowledge, this is the first explicit algorithm to compute the $3$-admissibility. The linear dependence on the input size in both time and space complexity, coupled with an `optimistic' design philosophy for the algorithm itself, makes this algorithm practicable, as we demonstrate with an experimental evaluation on a corpus of \\corpussize real-world networks. Our experimental results show, surprisingly, that the $3$-admissibility of most real-world networks is not much larger than the $2$-admissibility, despite the fact that the former has better algorithmic properties than the latter.","short_abstract":"The $3$-admissibility of a graph is a promising measure to identify real-world networks that have an algorithmically favourable structure. We design an algorithm that decides whether the $3$-admissibility of an input graph~$G$ is at most~$p$ in time~\\runtime and space~\\memory, where $m$ is the number of edges in $G$ an...","url_abs":"https://arxiv.org/abs/2512.01121","url_pdf":"https://arxiv.org/pdf/2512.01121v1","authors":"[\"Christine Awofeso\",\"Patrick Greaves\",\"Oded Lachish\",\"Felix Reidl\"]","published":"2025-11-30T22:26:36Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}