It is proved that any dataset admits a $\gamma$-almost navigable graph with just $O\left(\frac{n}{1-\gamma}\right)$ edges, linear in the dataset size, and a randomized algorithm for constructing such a graph in near-linear time is presented.
Abstract
Graph-based methods like HNSW, DiskANN, NSG, and others have become an increasingly popular choice for implementing approximate nearest neighbor search (ANNS) in Vector Databases (VecDBs). The success of these methods has motivated the study of how to best construct a search graph for a given dataset. To that end, \emph{navigability} has been identified as a desirable graph property which ensures good ANNS performance when combined with greedy search. However, for a dataset with $n$ vectors, the sparsest navigable graph requires $O(n\sqrt{n})$ edges in the worst-case, and we show empirically that, for typical billion node datasets, 100s of edges are needed per node. This leads to slow search and high memory requirements. Moreover, under standard complexity theoretical assumptions, it was recently established that constructing a sparse navigable graph requires $\Omega(n^{2-\epsilon})$ time, which is prohibitive for large datasets. We address these concerns by introducing a relaxed notation of navigability called ``$\gamma$-almost navigability''for any $\gamma \in [0,1]$, with $\gamma = 1$ corresponding to full navigability. We prove that any dataset (under any distance) admits a $\gamma$-almost navigable graph with just $O\left(\frac{n}{1-\gamma}\right)$ edges, linear in the dataset size. We present a randomized algorithm for constructing such a graph in near-linear time. While we prove that $\gamma$-almost navigability sacrifices the worst-case search guarantees enjoyed by navigability, we show empirically that greedy beam search still performs well in such graphs when $\gamma<1$. Indeed, we obtain improved recall-runtime tradeoffs on a variety of datasets compared to fully navigable graphs. Moreover, our graphs are more space efficient, with degree typically less than half that of a fully navigable graph for comparable performance.
Constructing special graphs is an important task within graph theory and computer science. Many popular graph constructions are the result of a comprehensive exploration of relevant graphs and human ingenuity. Given the rise of generative AI usage in mathematics, it is natural to test whether LLMs are able to construct graphs with specified properties using their reasoning capabilities. Unfortunately, many natural graph construction problems, such as finding extremal Ramsey-good graphs (i.e., avoiding specific monochromatic subgraphs), have been explored extensively in the literature, making it difficult to ascertain whether a construction is the product of an LLM's reasoning capabilities or its recollection from training data. In this work, we introduce \textbf{RamseyGadgets}, a novel dataset of 70 underexplored graph construction problems that require finding Ramsey-good graphs with special properties (e.g., containing an edge with a fixed color). These problems have reasonably sized solutions (at most 10 vertices) that can be verified by SAT solvers, making them suitable for automatic evaluation. Our dataset is easily expandable, as one can simply change the monochromatic subgraphs being avoided to obtain a new set of problems. We evaluate the performance of five open-source LLMs on our dataset and report the results. Our findings show that LLMs achieve only 37.70% accuracy on the hard-tier problems in our dataset, with Gemma-4-31B achieving the highest performance out of the five. We also showcase how our dataset allows us to ascertain what kind of hints help LLMs perform better at this task.
The findings indicate that the Eppstein-Wang algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.
Given a graph $G$ labeled with positive distances on each edge, what is the fewest number of edge distances that must be modified for $G$ to become a metric? It is known that this metric repair problem is $\mathrm{NP}$-hard on general graphs, with prior work focusing on approximations and fixed-parameter tractability with respect to properties of the input distance function. In this paper, we ask what structural properties of the graph itself make metric repair tractable. On the positive side, we give pseudo-polynomial time algorithms for series-parallel graphs, and by generalization, graphs of bounded treewidth. An immediate consequence of this result is a new algorithm for the length-bounded multicut problem, with a parameterized runtime bound in terms of the treewidth of a modestly augmented graph. Surprisingly, pseudo-polynomial time turns out to be the best one can hope for: We complement our algorithm with a proof that metric repair is weakly $\mathrm{NP}$-hard even on graphs of pathwidth at most six. We also prove that planarity does not help either, as the problem remains strongly $\mathrm{NP}$-hard even on grid graphs.
Asaf Etgar, Anna C.Gilbert, Jamie Tucker-Foltz· 0 citations
The planted subgraph detection problem asks whether a random graph contains a hidden structured subgraph. In the classical formulation, the entire adjacency matrix is observed and one distinguishes between an Erd\H{o}s--R\'enyi random graph and one obtained by planting a copy of a prescribed graph inside an Erd\H{o}s--R\'enyi random graph. The statistical and computational limits of this problem under full observation are now well understood, even for arbitrary planted subgraphs. In this paper, we investigate an information-limited version of the problem in which the planted structure is an arbitrary sequence of graphs $\Gamma=(\Gamma_n)_{n\geq1}$, where $\Gamma_n$ is embedded in an ambient graph on $n$ vertices, but the observer does not have access to the full adjacency matrix. Instead, information is acquired through a limited number of non-adaptive edge queries. We study the minimum query complexity required for reliable detection. We derive general information-theoretic lower bounds and complementary algorithmic upper bounds on the query complexity as functions of the query budget and structural properties of the planted graph. The proposed algorithms exploit three distinct structural mechanisms: dense local motifs, high-degree vertices, and global edge density. We establish matching bounds, up to polylogarithmic factors, for several broad families of planted graphs, including clique-like, bounded-cover, and hub-dominated graph classes. Our framework substantially generalizes existing query-complexity results for planted clique and planted dense subgraph models, providing a unified treatment of arbitrary planted subgraphs under restricted graph access.
We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes'labels. These graphs are widely used in bioinformatics to compactly describe large collections of highly similar genomes. Given such a graph $G=(V,E)$ and a pattern of length $m$, we seek a walk whose corresponding string has an occurrence of the pattern. We call this the SMLG problem. Amir et al. [J. Algorithms, 2000] showed that SMLG can be solved in $\mathcal{O}(m|E| + N)$ time, where $N$ is the total length of all node labels. Equi et al. [ACM Trans. Algorithms, 2023] showed that this is essentially optimal (under SETH). The existing lower bound assumes that the sought walk is of length $\Theta(|V|)$. Thus, we might be able to bypass this lower bound by restricting the walk length to $b-1$, which naturally reduces to having as input a directed graph whose set of nodes is partitioned into $b$ blocks. Then, we seek a walk in this graph that starts in the first block and ends in the last block. We call this the $b$-SMBG problem. We provide a more fine-grained classification that essentially settles the complexity of $b$-SMBG parameterized by $b$: (1) We give a near-linear-time algorithm for $b=3$. (2) We show that there is no combinatorial algorithm improving over the state-of-the-art $\mathcal{O}(m|E| + N)$ bound for any $b\ge 4$. (3) We also present a fast matrix multiplication-based algorithm yielding an improvement for $b \in \mathcal{O}(1)$, which is conditionally optimal. (4) Finally, we show that under SETH, for any $b \in \omega(\log |V|)$, no algorithm can improve over the state of the art.
Sebastian Angrick, B. Bals, Paweł Gawrychowski et al.· 0 citations
Introduced by Lee, Ko, and Shin (VLDB 2020), a hypergraph motif is a connected subhypergraph consisting of three hyperedges whose intersections satisfy a prescribed pattern. Such patterns are represented by Venn diagrams $\mathcal{V}\in\{0,1\}^7$, indicating which of the seven regions determined by three sets must be empty or non-empty. Lee et al. designed and implemented exact and approximate algorithms for counting, in a hypergraph $G$, the motifs specified by $\mathcal{V}$; their algorithms run in worst-case cubic time in the number of hyperedges of $G$. This cubic worst case can occur even for hypergraphs of bounded rank, and already for $2$-uniform hypergraphs, that is, for simple graphs. In this work, we give a complete fine-grained picture of the parameterised complexity of exact hypergraph motif counting with respect to the rank of the input hypergraph. We use $\tilde{O}$ to hide polylogarithmic factors in the input size. First, we show that every Venn diagram $\mathcal{V}$ admits an exact counting algorithm running in FPT-near-quadratic time, \[ f(\mathsf{rank}(G))\cdot \tilde{O}(|E(G)|^2), \] for some computable function $f$. Second, we precisely characterise when this can be improved to FPT-near-linear time. We prove that such an algorithm exists exactly for the degenerate Venn diagrams, namely those that force one of the three hyperedges to be fully contained in another. For all non-degenerate Venn diagrams, we show that no FPT-near-linear-time algorithm exists unless either the Triangle Hypothesis or the Hyperclique Hypothesis fails. Exact hypergraph motif counting is thus always fixed-parameter near-quadratic in the rank, and the degenerate Venn diagrams are precisely the cases admitting fixed-parameter near-linear time.