Papers for

network algorithm designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Directed graph convexities show contrasting complexity behaviors

The Monophonic Directed Convexities

Abstract: Graph Convexity is a topic with many papers in the literature, especially on the $P_3$, geodesic, and monophonic convexities in undirected graphs. Regarding directed graphs, Erd{\H o}s et al. in 1972 and Chartrand and Zhang in 2000 obtained the first results on the $P_3$ and geodesic convexities for directed graphs, respectively. In this paper, we start the investigation of monophonic convexity on directed graphs. We define two convexities, the monophonic and the strong monophonic directed convexities, related to the minimal and the induced directed paths, respectively. We show that deciding whether a set is convex is polynomial-time solvable in the monophonic convexity, but coNP-complete in the strong monophonic convexity. For both convexities, we prove that the hull number is NP-complete even in DAGs. Regarding the monophonic convexity, we prove that the hull number is polynomial time solvable in tournaments, but the interval number is NP-complete in tournaments and also in bipartite oriented graphs.

Tue 10 NovComputational Complexity
The gist
The paper studies special ways to find groups of related points in directed networks, called monophonic convexities. The authors introduce two types, one easier to check and another much harder, based on different kinds of paths. They show that some problems about these groupings are tough to solve on general networks, but easier on special cases like tournaments. This work helps understand which network properties can be efficiently analyzed depending on the type of directed paths considered.
Open → 2611.14191v1

Rotating walks and derandomized squares reveal new graph behaviors

Rotating Walks, Derandomized Squares, and Permutation Conjugated Walks

Abstract: Using the recent strong convergence results of Bordenave and Collins (Annals of Mathematics) and Chen et al. (Annals of Mathematics), we study the average case behavior of rotating random walks of Cohen and Maor (STOC 2023) and the derandomized square construction of Rozenman and Vadhan (RANDOM 2005). Concretely, we prove a conjecture of Cohen et al. (ITCS 2025) regarding the average case behavior of derandomized squaring for random graphs and show that the existential bounds of Cohen and Maor for their rotating random walk construction hold with high-probability for random graphs. Using the results of O'Donnell and Wu (FOCS 2020), we can in polynomial time construct a family of graphs and rotations which almost saturate the bounds of Cohen and Maor, and meet the bounds conjectured by Cohen et al. for all vertex-transitive auxiliary graphs of fixed degree in the derandomized square. Finally, we study independent random permutation conjugates of deterministic regular graph adjacency matrices. We prove quantitative weak convergence to freely independent tree adjacency operators when the degrees are fixed and the girths tend to infinity. Separately, a covering argument gives deterministic spectral lower bounds for polynomials with non-negative coefficients, recovering the lower bound of Cohen et al. for rotating walks.

Tue 10 NovDiscrete Mathematics
The gist
This paper deals with special ways of walking through networks (graphs) to understand how they behave on average. The authors prove some earlier guesses about how certain graph constructions work when the graphs are random. They also show how to build specific graphs that nearly match these ideal behaviors. Finally, they study how mixing random shuffles with fixed patterns affects the graph’s properties, especially in large and complicated network structures.
Open → 2611.13693v1

Induced packing branchwidth links graph structures and decompositions

Induced packing treewidth III. Branch decompositions

Abstract: The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. In this paper, we introduce induced packing branchwidth, a branch-decomposition analogue of induced packing treewidth. For a graph $H$, the induced $H$-packing branchwidth of a graph $G$, denoted by $\branchpi_H(G)$, is the minimum, over all branch decompositions of $G$, of the largest number of pairwise anticomplete induced copies of $H$ that cross one displayed cut. For $H=P_2$, it equals sim-width. We prove several structural properties of graphs of bounded $\branchpi_H$, for various choices of $H$, including $χ$-boundedness, polynomial degree-boundedness, and metric properties.

Mon 9 NovDiscrete Mathematics
The gist
This work studies a new way to measure structural complexity in networks called induced packing branchwidth. The authors connect this measure to existing concepts that describe how graphs can be broken into simpler pieces while avoiding certain patterns. They also show how graphs with small values of this measure have useful properties, like constraints on colorings and distances. This helps unify different approaches to understanding complicated networks.
Open → 2611.12358v1

New sequences improve treasure hunt speed in network graphs

Faster Treasure Hunt via Strongly Universal Exploration with Polylogarithmic Overhead

Abstract: We study deterministic exploration and delayed-activation treasure hunt in anonymous undirected port-labeled graphs with incoming-port information. From polynomial-time constructible ordinary universal exploration sequences of length \(O(n^c)\) for a fixed regular degree, we construct a single infinite strongly universal exploration sequence with cover time \(O(n^c\log^2n)\). Summable dyadic insertion schedules yield the sharper bound \(O_\eps(n^c\log n(\log\log n)^{1+\eps})\) for every fixed \(\eps>0\), together with refinements at every fixed iterated-logarithm depth. The proof combines reversible excursions, neutral guards and an arbitrary-window argument that treats both orientations simultaneously. For this recurrence, uniform linear expansion is equivalent to convergence of the normalized period sum. Exact counting identities also permit direct instruction access. With a logspace ordinary generator, table-free enumeration of decreasing scale paths computes instruction \(t\) using \(O(\log(t+2))\) working bits and time polynomial in \(t\). The earlier polynomial-slack bounds follow as corollaries. A local cubic simulation extends the treasure-hunt application to arbitrary-degree graphs, with the \(2m\)-vertex replacement size included explicitly in the bound.

Thu 5 NovComputational Complexity
The gist
This paper deals with how to explore all nodes in a network efficiently, even when the network has no labels and special information is only partially available. The authors create a special kind of sequence that guides exploration in any network, improving previous methods by adding only a small extra cost. Their approach uses clever mathematical tools like reversible trips and careful scheduling to cover all parts of the network faster. They also extend their results to networks where nodes can have any number of connections.
Open → 2611.08705v1

Efficient model checking for graphs with metric logic extensions

Model Checking for Metric Extensions of Monadic Second-Order Logic

Abstract: Monadic second-order logic yields powerful algorithmic meta-theorems, but cannot express that a vertex set induces a shortest path. We study metric extensions of counting monadic second-order logic and identify structural parameters supporting efficient model checking, optimization, and counting. We show that shortest paths and equidistance guarded by geodesic cycles are definable in ordinary vertex-set MSO on graph classes of bounded cycle-basis length. This yields fixed-parameter tractable model checking for the corresponding extensions of CMSO2, parameterized by formula length and bag-connected treewidth, and of CMSO1, parameterized by formula length and geodesic cliquewidth: the sum of cliquewidth and cycle-basis length. The translations preserve free variables, yielding additive optimization and counting. Applications include Minimum Geodetic Set and Strong Metric Dimension for geodesic cliquewidth, and Minimum Isometric Path Partition for bag-connected treewidth. We also introduce restricted packing-covering templates that allow numerical distance thresholds to remain outside the parameter. For each fixed template, feasibility, additive vertex-weight optimization, and counting are fixed-parameter tractable in bag-connected treewidth. Applications include Distance-r Dominating Set, d-Scattered Set, and Minimum Eccentricity Shortest Path. Finally, we characterize bounded bag-connected treewidth and bounded geodesic cliquewidth through monadic dependence for the corresponding guarded logics. Unguarded distance comparisons have stricter structural boundaries: first-order model checking is AW[*]-complete already on uncolored caterpillars, and model checking a fixed existential monadic sentence is NP-complete on this class.

Fri 30 OctLogic in Computer Science
The gist
Graphs are networks made of points connected by lines, and sometimes it’s important to find special paths or distances in them. However, usual logical tools can’t easily express things like shortest paths. This paper studies extended logical frameworks that add distance and counting capabilities, and identifies ways to efficiently check logical statements about graphs with certain structures. The authors also connect these new methods to how complex or simple the graph is, helping decide when such checks are computationally manageable.
Open → 2610.41974v1

Optimal embeddings improve graph cuts and expansion approximations

Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion

Abstract: We show that any $n$-point Euclidean metric admits a non-expansive embedding into the line with average distortion at most $O\left(\sqrt{\frac{\log n}{\log\log n}}\right)$, matching a known lower bound. We also present two applications of this result. First, we give a cut-player strategy with an optimal spectral guarantee for the undirected cut-matching game. Second, we give an improved spectral approximation for vertex expansion in high-degree graphs.

Fri 30 OctData Structures and AlgorithmsComputational Geometry
The gist
The paper deals with a way to represent distances between points in a space using just a line, without stretching the distances too much on average. The authors find the best possible way to do this for points in ordinary Euclidean space, matching what was previously known as a minimum limit. They then show how this finding helps create better strategies to split networks into parts efficiently and to estimate how connected nodes are in complex graphs.
Open → 2610.41945v1

Online and low-degree algorithms find half-size induced matchings in random graphs

Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms

Abstract: For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp within broad algorithmic classes. We prove such a gap for finding large induced matchings in Erdős-Rényi random graphs. In the worst case, requiring a matching to be induced turns a polynomial-time solvable problem into an NP-hard one; our results reveal an average-case counterpart. In $G(n,p)$ with $C/n\le p\le 1-κ$, the largest induced matching has size $(1+o(1))L$ with high probability, where $L=\log_{1/(1-p)}(np)$. A simple online greedy algorithm finds an induced matching of size $(1/2-ε)L$, while no online algorithm, even with adaptive inspection order and unbounded computation, finds one of size $(1/2+ε)L$ except with probability $\exp(-Ω(L\log(np)))$. In the sparse regime $p=d/n$, low-degree polynomial algorithms exhibit the same sharp threshold. Our guarantees rest on a maximality principle: with high probability, every maximal induced matching is half-optimal. Greedy outputs a maximal induced matching and our low-degree algorithm a near-maximal one. We bypass the delicate coupling arguments classically used to analyze greedy since Karp. For low-degree hardness, we adapt Wein's overlap gap argument, with forbidden structures that track overlaps between endpoint sets rather than edge sets, since a new edge may join two previously used endpoints and thus encounter no fresh randomness. For online hardness, we give a new and significantly simpler argument that avoids the correlated instances of prior OGP-based proofs: at a suitable stopping time, all pairs involving uninspected vertices remain unrevealed, so a direct first-moment bound suffices.

Thu 29 OctData Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
The gist
Finding the largest set of edges in a network where no two edges share a vertex and are connected only to each other (an induced matching) is really hard in general. The authors show that in random networks, simple methods like greedy online algorithms can reliably find induced matchings that are about half the maximum possible size, and no online approach can do significantly better. They also prove that certain low-degree polynomial algorithms share this half-optimal limit. Their work uses new mathematical ideas to avoid complicated traditional proofs and shows that this half-size limit is a fundamental barrier for these algorithm types.
Open → 2610.40369v1

Optimal regret bounds achieved for decentralized online learning

Optimal Regret for Communication-Efficient Decentralized Online Learning

Abstract: In this paper, we investigate decentralized online convex optimization with compressed communication, where $n$ learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are $O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n})$ and $O(ω^{-1}nρ^{-2}\ln n\ln T)$ for convex and strongly convex loss functions, respectively, where $ρ\in(0,1)$ is the spectral gap of the communication matrix and $ω\in(0,1]$ is the compression quality factor. Compared with the corresponding lower bounds of $Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $Ω(ω^{-1}nρ^{-1/2}\ln T)$, these upper bounds exhibit polynomial gaps in their dependence on $ρ^{-1}$. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of $\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $\widetilde O(ω^{-1}nρ^{-1/2}\ln T)$ for convex and strongly convex loss functions, respectively. Up to logarithmic factors in $n$ and $ρ^{-1}$, these results match the lower bounds in terms of $T$, $n$, $ρ$, and $ω$.

Wed 28 OctMachine Learning
The gist
This paper deals with teaching many computers working together how to learn from data that changes over time, using limited communication between them. Previous methods had inefficiencies in how fast the computers could agree and learn, measured by something called regret. The authors improved these methods by developing a new communication technique called Ascent-gossip that speeds up consensus while using compressed messages. Their final algorithm reaches the best possible performance in how quickly it learns, matching theoretical limits except for some small technical factors.
Open → 2610.38334v1

Linear kernel method improves semitotal domination problem on planar graphs

A Linear Kernel for Planar Semitotal Domination

Abstract: A set of vertices $S$ in a graph $G$ is a semitotal dominating set if $S$ is a dominating set and every vertex in $S$ has a witness, that is, another vertex in $S$ within distance at most two. The Semitotal Domination problem asks whether $G$ admits such a set of size at most $k$. We study this problem parameterized by the solution size. We provide a linear kernel of size $358k$ on planar graphs, a result that adds to several existing linear kernels for other domination variants on planar graphs. Additionally, we show Semitotal Domination is $W[2]$-hard on split graphs, on bipartite graphs and on $t$-claw-free graphs, it is $W[1]$-hard on circle graphs.

Tue 27 OctData Structures and Algorithms
The gist
The semitotal domination problem involves finding a special group of nodes in a network where each node covers others and is close to another in the group. The authors show a way to simplify this problem for flat networks (planar graphs) by shrinking it to a size proportional to the allowed group size. They also prove that this problem remains very hard for several other types of networks. This work helps better understand which network types allow efficient simplifications and which do not.
Open → 2610.37295v1

Space needed for fast approximate distances in sparse graphs

Tight Space Bounds for Pivot-Based Distance Oracles in Sparse Graphs

Abstract: An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative \emph{stretch} $k$. The classical oracle of Thorup and Zwick~[STOC'01, JACM'05] has stretch $k=2\ell-1$ and uses $O(\ell n^{1+1/\ell})$ space, for every integer $\ell\ge1$, and this trade-off is optimal for dense graphs under the Erdős girth conjecture. However, for sparse graphs ($m=O(n)$), their lower bound yields nothing beyond $Ω(m)$ space. A pivot-based $1$-hop ADO gives every vertex $\tilde{O}(1)$ pivots and returns as an estimate the length of a walk of the form $u\to p_u \to p_v \to v$, where $p_u$ is a pivot of $u$, $p_v$ is a pivot of $v$, and $p_u\to p_v$ is a stored distance. We observe that all the state-of-the-art ADOs with $\tilde{O}(1)$ query time are in fact pivot-based $1$-hop ADOs. Our main result is that, under the Erdős girth conjecture for graphs with constant degree, there are sparse graphs on which every \emph{pivot-based} $1$-hop ADO with stretch $k$ requires $\widetildeΩ(m^{1+2/(k+1)})$ space, for every \emph{real} $k\ge1$. This matches the best known upper bounds with $\tilde{O}(1)$ query time, up to polylogarithmic factors, at every stretch where they are known. We also extend our lower bound to pivot-based ADOs with any constant number $β$ of hops, showing that they require $\widetildeΩ(m^{1+2/(β(k+1))})$ space. In addition, we obtain a tight lower bound for two-hop hopsets. Under the Erdős girth conjecture, for every integer $\ell\ge3$, $(2\ell-3,2)$-hopsets on sparse graphs require size $Ω(m^{1+1/\ell})$, which matches a construction based on the oracles of [Kadria and Roditty, ISAAC'25]. Using the recent explicit high-girth graphs of Double Agent~[doubleAI'26], we also obtain unconditional versions of our ADO lower bounds, with the exponent above $1$ multiplied by $4/5$.

Wed 21 OctData Structures and Algorithms
The gist
This paper studies how much computer memory is required to quickly estimate distances between points in networks that have few connections. The authors focus on a common approach that uses special reference points called pivots to approximate distances within a certain accuracy level. They find that for networks with few connections, there is a near-limit to how compact these pivot-based structures can be, proving that past constructions are essentially optimal under well-known mathematical assumptions. They also extend their findings to allow slightly more complex queries and provide unconditional results based on recent graph constructions.
Open → 2610.29624v1

Annotated graph parameters unified by torsos simplify structural analysis

Invitation to torso parameters of annotated graphs

Abstract: An annotated graph is a pair $(G,S)$, where $G$ is a graph and $S$ is a subset of vertices of $G$. We present a unified approach for definitions of annotated versions of classical graph parameters such as treewidth, pathwidth, treedepth, etc. A generic way to incorporate a distinguished set of vertices into a graph parameter is via torsos. Given a graph $G$ and a subset $S'\subseteq V(G)$, we define $\mathrm{torso}_G(S')$ to be the graph with vertex set $S'$ in which distinct vertices $u,v\in S'$ are adjacent if and only if there exists a $u$-$v$ path in $G$ whose internal vertices lie outside $S'$. Now let $\mathrm{p}$ be any graph parameter. For an annotated graph $(G,S)$, we define the torso $\mathrm{p}$ of $(G,S)$ by \[\mathrm{p}(G,S) = \min\{\mathrm{p}(\mathrm{torso}_G(S')) \mid S \subset S' \subset V(G)\}.\] For a minor-closed class of annotated graphs $\mathcal{C}$, we discuss equivalent conditions for $\mathrm{p}(G,S)$ bounded for all $(G,S)\in\mathcal{C}$ in terms of annotated graphs excluded in $\mathcal{C}$. In many cases, we collect known results from the literature. We include two new arguments for $\mathrm{p}$ being the $2$-treedepth and the feedback vertex number. Among other statements, we also include a variant of the Erdős-Pósa property for annotated cycles. We propose some new research directions.

Mon 19 OctDiscrete Mathematics
The gist
Many problems in computer science can be understood by studying graphs, which are like networks of points connected by lines. Sometimes, certain points are marked as special, and analyzing these marked networks is tricky. The authors introduce a new way to look at these marked points by focusing on smaller, simpler parts of the graph called torsos. This lets them define and study many network measurements in a unified way and connect these measurements to known graph properties and classes. They also explore some new theoretical connections and suggest future research directions.
Open → 2610.25905v1

Fast method solves edge-claiming claw game on graphs with degree 4

A Linear-Time Algorithm for the Unbiased Claw Game on Graphs with Maximum Degree 4

Abstract: We study the unbiased Maker-Breaker $K_{1,3}$-game, the unbiased claw game, played on the edge set of a general graph $G$. In this game, Maker and Breaker alternatingly claim edges of $G$, and Maker wins if his claimed edges contain a claw once no more edges are available. Graphs with maximum degree at least 5 are Maker's win. A graph $G$ is claw-connected if the hypergraph modeling the unbiased claw game played on $G$ is connected. We characterize Maker's win in the unbiased claw game on every claw-connected graph whose maximum degree is different from 3. Our main structural result is a complete characterization of Maker's win for claw-connected graphs with exactly one vertex of degree 4. The analysis is based on the fact that vertices of degree 4 act as forcing structures. Our characterization results in a linear-time algorithm for the unbiased claw game on claw-connected graphs with maximum degree different from 3. We also obtain a linear-time decomposition algorithm reducing the game on general graphs to a collection of pairwise edge-disjoint claw-connected subgraphs of maximum degree exactly 3, thereby isolating the only remaining case. This decomposition yields an $\mathcal{O}(|V(G)|^3)$-time algorithm for the unbiased claw game on general graphs, improving on the $\mathcal{O}(|V(G)|^7)$-time algorithm implied by the work of Galliot, Gravier and Sivignon (arXiv 2026). For a lower bound on the decision complexity, we prove that any agent deciding the game in the adjacency-array model makes at least $Ω(|V(G)|)$ queries in the worst case, indicating the optimality of our linear-time algorithm.

Thu 15 OctDiscrete Mathematics
The gist
This work studies a game played on a network where two players alternately claim connections (edges). One player wins if they can form a specific small shape resembling a claw. The authors fully describe when this player can win on networks with nodes connecting up to four edges, focusing especially on networks with just one node connected to four others. They provide a quick, step-by-step method to decide the winner in these cases, and a way to break down any network into smaller parts so the problem can be solved more easily. They also show their method is as efficient as possible, needing only a number of checks proportional to the size of the network.
Open → 2610.21878v1

Generalized total variation improves federated learning with large data

A Large-Dimensional Analysis of Least-Squares Federated Learning via Generalized Total Variation Minimization

Abstract: Federated learning over decentralized networks inherently trades off the suppression of local finite-sample noise through collaboration against the bias that collaboration introduces between heterogeneous nodes. We study this tension by performing a large-dimensional analysis of Generalized Total Variation Minimization with least-squares models. Using tools from random matrix theory, we show that Lipschitz observations of the global GTVMin solution concentrate in large dimensions, universally for any underlying network structure. We provide exact analytic expressions for the asymptotically precise performance under both i.i.d. and non-i.i.d. Gaussian mixture distributions on a fixed network. For the latter, these expressions quantify how regularization balances local adaptation against collaboration. Our theoretical results are confirmed by experiments on synthetic and real-world data.

Wed 14 OctMachine Learning
The gist
Federated learning lets different computers work together to train a shared model without sharing their raw data. However, this collaboration can introduce bias when the computers have different types of data. The authors studied this trade-off using a mathematical approach called Generalized Total Variation Minimization with least-squares models. They found precise formulas describing how well this method works with large amounts of data and different network setups. Their findings help understand how to best balance collaboration and local data differences, and they confirmed their theory with experiments.
Open → 2610.20075v1

Non-clashing teaching complexity in planar graph neighborhoods bounded

On Collusion-Free Teaching in Planar Graphs

Abstract: Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman--Mathias collusion-avoidance criterion. While the Vapnik--Chervonenkis dimension (VCdim) measures the complexity of learning from samples, non-clashing teaching dimension (NCTD) measures the number of examples required when a teacher can select them. Whether NCTD is always bounded above by VCdim remains a fundamental open question in learning theory. In this paper, we investigate this question for the concept classes of closed neighborhoods in planar graphs. We prove a tight upper bound of two on their NCTD, thereby establishing the conjectured inequality for this family. For the positive variant NCTD+, in which teaching sets contain only positive examples, we obtain a tight upper bound of four. Finally, we show that deciding whether either NCTD+ or NCTD is at most one is NP-complete, even for concept classes of closed neighborhoods in planar graphs. In particular, despite the upper bound of two on NCTD for such classes, distinguishing between NCTD values of one and two remains NP-hard.

Tue 13 OctDiscrete MathematicsComputational ComplexityMachine Learning
The gist
Teaching a computer to recognize patterns often requires showing examples. There is a way to measure how many examples a teacher needs without confusing the learner by colluding. This paper studies such teaching in shapes made from networks drawn on a flat surface, called planar graphs. The authors found exact limits on how many examples are needed and showed that figuring out some cases is very hard, even in simple network shapes.
Open → 2610.18714v1

Graph search tree leaf count optimization remains complex for lexicographic DFS

On Kernels and Leaves: Searching for Bare and Lush Trees

Abstract: We study a variation of the classical Maximum (Minimum) Leaf Spanning Tree problem. In many applications, Depth-First Search (DFS) is used to compute a spanning tree of a graph. Such a search tree is constructed by connecting each vertex $v$ with the last vertex the search has visited before $v$ and we call this a last-in tree. By restricting the Maximum (Minimum) Leaf Spanning Tree problem to last-in trees of a graph search, we ask for a search ordering that leads to the largest (smallest) number of leaves in its search tree. Recently, Bergougnoux et al. [Journal of Computer and System Sciences 154 (2025)] have studied the parameterized complexity of these problems for DFS. They showed that the minimization problem is para-$\mathsf{NP}$-hard and the maximization problem is $\mathsf{W}[1]$-hard when parameterized by the number of leaves. When parameterized by the number of internal vertices, both problems have polynomial kernels. Here, we examine whether these results also hold for the variant Lexicographic DFS (LDFS). We show that the hardness results of DFS can be transferred to LDFS. We also present exponential kernels for the number of internal vertices as the parameter. We complement this by showing that polynomial kernels do not exist, unless $\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}$. We also consider last-in trees of searches that do not follow the DFS scheme. In contrast to (L)DFS, minimizing the number of internal vertices is para-$\mathsf{NP}$-hard for several searches including Breadth-First Search.

Thu 24 SeptData Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
The gist
The paper looks at how to find a path through a network (a graph) that makes the resulting search tree have the most or fewest endpoints (leaves). Normally, a Depth-First Search (DFS) method builds this tree in a specific way, but the authors study a variant called Lexicographic DFS (LDFS). They find that the hard problems for DFS—deciding if you can get many or few leaves—remain just as hard in LDFS. They also show some limits on how much these problems can be simplified (kernelization). Finally, they consider other search methods and find that minimizing certain tree properties can be very hard for those too.
Open → 2609.29451v1

Quantum algorithm colors cycle graphs in constant time

Quantum Advantage for Distributed Symmetry Breaking

Abstract: We present a distributed quantum algorithm that $3$-colors cycles in $O(1)$ rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have round complexity $O(\log^* n)$ in the classical LOCAL model can be solved in $O(1)$ rounds in the quantum-LOCAL model, with high probability; this includes problems such as maximal independent set and maximal matching in bounded-degree graphs. This presents the first natural examples of graph problems with an asymptotic distributed quantum advantage for the LOCAL model; all prior examples that separate LOCAL and quantum-LOCAL are artificial problems constructed merely for the sake of demonstrating quantum advantage.

Tue 22 SeptDistributed, Parallel, and Cluster Computing
The gist
Some network problems require nodes to pick colors or labels without conflicts, which can be slow on classical computers. The authors show that quantum computing can solve these problems much faster in a distributed setting, specifically coloring cycle graphs with three colors in constant time. This speed-up works for many related problems where classical methods take longer, marking the first natural instance where quantum networks outperform classical ones. This suggests quantum communication can fundamentally improve distributed coordination tasks.
Open → 2609.26788v1

Integral graphs with unique patterns found from groups and recursive builds

Structural Characterizations and Algebraic Realizations of a Family of Regular Integral Graphs

Abstract: All the eigenvalues of an integral graphs are integers. Integral graphs are extremely rare. They form an asymptotically vanishing fraction $2^{-Ω(n)}$ among all graphs on $n$ vertices. It makes the construction of a new family of integral graphs a challenging task. Also, most of the known infinite family of integral graphs rely on Cayley graphs over Abelian groups. In this article, we introduce a new family of integral graphs obtained from the groups. The construction of our graphs from groups is different from the construction of Cayley graphs. A spectral uniqueness theorem is established, which shows that each member of the infinite family is determined by its adjacency spectrum among all finite simple graphs. We also present recursive constructions that generates larger members of the family from smaller ones, providing a scalable class of integral graphs. Finally, we investigate algebraic realizations of these graphs as complements of Proper Prime Order Element Graphs of finite $2$-groups and obtain conditions characterizing such realizations. We also observe that the graphs obtained from different non-isomorphic groups have cospectral graphs.

Tue 22 SeptDiscrete Mathematics
The gist
Integral graphs have all their special numbers, called eigenvalues, as whole numbers, which is very rare. Most known integral graphs come from a certain kind called Cayley graphs, but the authors found a new way to build them using groups differently. They showed that each graph in their new family can be uniquely identified just by looking at these special numbers. They also found ways to make bigger integral graphs from smaller ones, and studied connections to special group-based graphs, even finding some that share these special numbers despite looking different.
Open → 2609.25957v1

Planar directed graphs simplified by removing few vertices to avoid cycles

A Polynomial Kernel for Planar Directed Feedback Vertex Set

Abstract: The Directed Feedback Vertex Set problem (DFVS) asks whether a digraph can be made acyclic by deleting at most $k$ vertices. Whether DFVS admits a polynomial kernel parameterized by $k$ is a major open problem in kernelization, even for planar digraphs. We resolve the planar case by giving a deterministic kernel with $O(k^{66}\log^2 k)$ vertices and arcs. Our algorithm proceeds in three stages. First, we apply structural reduction rules to the input digraph, bounding the number of directed faces and some special vertices. Second, we pass to the planar dual, where vertex deletion corresponds to adding groups of reverse arcs to make each weakly connected component strongly connected. The structural bounds in the first stage yield a small retained vertex set in the dual. We then compress the dual instance by identifying vertices with the same distance records from this retained vertex set. The main technical contribution is a directed-cut argument showing that this identification preserves feasibility. Finally, we transform the polynomial-size dual instance back into an instance of Planar Directed Feedback Vertex Set via a $3$-CNF encoding and a planar graph construction.

Sun 20 SeptData Structures and Algorithms
The gist
The problem tackled is figuring out if a directed network (digraph) can be made free of loops by removing a small number of nodes. The authors provide a way to shrink such planar networks into a much smaller version without changing the answer to this problem. They do this by clever steps including simplifying the graph, switching perspectives to its dual, and compressing repeated patterns while keeping the problem’s solution intact. This leads to a smaller, manageable instance that still accurately represents whether the original network can be made loop-free.
Open → 2609.23669v1

Distributed algorithms optimize functions without curvature limits

Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds

Abstract: This work addresses decentralized online Riemannian optimization on Hadamard manifolds. Prior work under geodesic convexity (g-convexity) may require curvature information in the optimization analysis, typically through a finite lower bound on the sectional curvature. Curvature may also enter the step size or contraction factor of tangent-space Riemannian consensus schemes. In this work, we relax the curvature dependence for a narrower class of horospherical convex (h-convex) functions. We study Distributed Riemannian Online Gradient Descent (D-ROGD), which combines local Riemannian h-subgradient updates with an implicit Fréchet-mean consensus. For h-convex and strongly h-convex local objectives, we establish $O(\sqrt{T})$ and $O(\log T)$ static regret, respectively, matching the corresponding Euclidean rates with respect to $T$, with network dependence governed solely by the spectral gap. To our knowledge, these are the first curvature-independent regret guarantees for decentralized online optimization on Hadamard manifolds. Experiments on hyperbolic embeddings corroborate the predicted rates, with no observable degradation due to curvature.

Sat 12 SeptMachine Learning
The gist
This paper looks at how to solve optimization problems across a network when the space has certain curved shapes, called Hadamard manifolds. Previous methods needed to know details about the space’s curvature to guarantee good performance. The authors find a way to guarantee good learning performance without needing curvature information for a narrower type of function called horospherical convex. Their method achieves performance similar to that on flat spaces, and experiments with hyperbolic data support their findings.
Open → 2609.13646v1

Four connected graphs found without legal systems despite positive curvature

A Four-Connected Graph without a Legal System

Abstract: In a 2021 paper, Jankiewicz, Norin, and Wise asked whether there exists a finite $4$-connected graph of girth at least four and nonnegative Charney--Davis curvature such that no $4$-connected ordinary subgraph admits a legal system. We construct such a graph by starting from the hexagonal prism and attaching three $K_{3,4}$-based caps along pairwise disjoint induced $4$-cycles. The key structural input is a restriction theorem showing that a legal system on an induced-$4$-cycle amalgam restricts to each side, so the obstruction carried by the negatively curved prism survives the attachments. The resulting $33$-vertex graph is $4$-regular and $4$-connected, has girth four and Charney--Davis curvature one, and, by $4$-regularity, is its own unique $4$-connected ordinary subgraph.

Fri 11 SeptDiscrete Mathematics
The gist
The paper answers a complex question about a special type of network called a 4-connected graph. The authors show that there exists a particular network with certain properties—like having no small loops and a positive curvature measure—but still does not have a 'legal system,' a kind of substructure researchers study. They build this example starting from a known shape called a hexagonal prism and attach special parts to it. This construction proves that their example behaves uniquely in the way they asked about.
Open → 2609.13419v1