CS Paper Radar

EPPA for Reducts of the Random Graph

Sofia Brenner, Jan Hubička, Matěj Konečný

cs.DM math.COmath.LO ·submitted 2026-10-29 10:13 UTC · v1
theory

Abstract

We prove that finite two-graphs have coherent EPPA and that neither graphs modulo global complementation nor two-graphs modulo global complementation have EPPA. This completes the classification of EPPA and coherent EPPA for the reducts of the random graph, answering a question and confirming a conjecture of Evans, Hubička, Konečný and Nešetřil.

Closest papers

Nearest neighbours by meaning across the whole index.

Non-induced inherent graphs

cs.DM math.CO ·2026-11-04 ·Vladimir Gurvich, Matjaž Krnc, Martin Milanič, Mikhail Vyalyi
similarity 0.58
Abstract

Concepts of avoidable paths and inherent two-rooted graphs were recently introduced for the case of induced subgraphs. In this paper, we translate this framework to the setting of not necessarily induced (NNI) subgraphs, where the structural constraints, as well as conclusions, are significantly relaxed. We develop a new sufficient condition for inherence, and use it to provide complete characterizations of inherent two-rooted paths and forks. We show that for these families, the obvious necessary condition for inherence from the induced case is sufficient in the NNI setting. To complement these results, we introduce two general methods for proving non-inherence and apply them to demonstrate the non-inherence of several classes of two-rooted trees. Keywords: subgraph, two-rooted graph, two-rooted tree, avoidable two-rooted graph, inherent two-rooted graph

0.25

Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$

cs.DM cs.DSmath.CO ·2026-10-30 ·Yanyu Chen, Yu Chen
theory similarity 0.57
Abstract

Given a simple undirected graph on $n$ vertices, random $k$-out sampling forms a spanning subgraph by having each vertex independently choose $k$ incident edges uniformly with replacement. We prove that, for every integer $k\geq2$, the expected number of original edges joining distinct sampled components is $O(n/k)$. This resolves the conjecture of Holm, King, Thorup, Zamir, and Zwick in its full range, improving their logarithmic sampling requirement to the optimal threshold of two choices per vertex. The bound fails for $k=1$, and the dependence $O(n/k)$ is tight up to constant factors. Our result holds with replacement and consequently also without replacement. In particular, this implies that contracting just two independent local choices per vertex suffices to reduce an arbitrary simple graph to a quotient with $O(n)$ edges in expectation, which is crucial in reducing the instance size for many contraction-based algorithms. Our proof uses switching arguments to relate intercomponent edges to bridges and a degree-weighted component potential, whose expectation we also bound with a switching argument.

0.26

Global Trace Condition for Injective Transition Graphs

cs.LO ·2026-11-03 ·Stefano Berardi, Ugo de'Liguoro, Daniel Osorio-Valencia
theoryhot direction similarity 0.56
Abstract

We formulate the global trace condition, GTC, for cyclic proofs as a particular case of the size-change termination condition, or SCT. We express cyclic proofs through a variant of size-change graphs, called transition graphs, whose edges are labelled by (finite) bipartite relations. We show that injective transition graphs suffice to encode cyclic pre-proofs for a variant of Brotherston and Simpson's sequent calculus with inductive definitions. The injectivity of transition graphs corresponds to restricting SCT to fan-in-free graphs. Then we prove that an essentially weaker condition implies SCT in this case, and hence GTC.

0.33

Local Convergence of Triadic Closures of Sparse Random Graphs

cs.DM math.PRmath-phmath.CO ·2026-10-29 ·Himasish Talukdar
theory similarity 0.56
Abstract · 46 pages, 4 figures

Triadic closure is a natural mechanism for modeling the clustering phenomenon observed in many real-world networks. Given a possibly random undirected graph $H$, we consider pairs of non-adjacent vertices that have a common neighbor. Conditional on $H$, each such pair is joined by an edge independently and simultaneously, with a probability depending on the degrees of its endpoints and on the number of their common neighbors. The resulting graph is called a triadic closure of $H$. We study the effect of this operation on local convergence. More precisely, we prove that if a sequence of potentially random finite undirected graphs of $\left( H_n \right)_{n \in \mathbb{N}}$ converges locally in probability to a rooted graph $H^*$, then the corresponding sequence of triadic closures converges locally in probability to the same triadic closure of $H^*$. As a consequence, we obtain a general limit theorem for the clustering coefficients of triadic closures. In particular, we show that the triadic closures can have a strictly positive limiting clustering coefficients even when the limiting clustering coefficients of the parent graph sequence is zero. Finally, we apply our results to several classical sparse random graph models including Erdős-Rényi, configuration, preferential attachment models and compute the limiting clustering coefficients of their triadic closures.

0.36

Correlation Clustering with Random Partial Information

cs.DS cs.LG ·2026-08-17 ·Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari
theory similarity 0.56
Abstract · 17 pages, 5 figures, 6 tables

Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.

0.26

On the Critical Window for Adaptable 2-Colorability

cs.DM math.CO ·2026-09-10 ·Thomas Snow
theory similarity 0.56
Abstract · 37 pages; typo corrected in reference

We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of the edges. To accomplish this, we characterize a family of subgraphs along with edge colorings whose inclusion or exclusion determines adaptable $2$-colorability. We further show that above the threshold, a long path with alternating edge colors is formed. We use this path to prove the existence of such a subgraph in the supercritical regime. We then provide and prove symmetric bounds on the critical window for $2$-adaptable colorability. Particularly, we prove bounds matching that of the critical windows for the giant component in the Erd$ő$s-R$é$nyi random graph model as well as the satisfiability of a random $2$-SAT instance. Finally, we show that below the critical window, the solution space of adaptable $2$-colorings remains connected, that is one can travel from one adaptable $2$-coloring to another by a sequence of $2$-colorings which differ on $O(\log{n})$ many vertices.

0.21

Two-Sample Testing for Random Graphs without Vertex Correspondence

cs.LG stat.ML ·2026-10-05 ·Soham Dan
theory similarity 0.56
Abstract

Two populations of graphs often have to be compared without any correspondence between their vertices, for instance when networks come from different communities, or when a graph generative model is evaluated against held-out graphs. We study how many graphs such an unaligned two-sample test needs, and which graph statistics can detect which differences. For an Erdős--Rényi null and a planted two-block difference that leaves every expected degree unchanged, we show that $m\asymp t^{-3}$ graphs per group are necessary and sufficient when the per-graph signal-to-noise ratio is $t<1$. Signed triangle counts attain this rate, and the lower bound holds for every graph size. With aligned vertices $m\asymp t^{-1}$ graphs suffice, so misalignment costs a factor of order $t^{-2}$. When the triangle signal cancels, the rate becomes $t^{-4}$ and $4$-cycles are needed. Statistics built from trees have exactly the same expectation under both hypotheses, and tests based on finitely many of them have asymptotically no power. In the graphon limit, this class includes degree distributions and message-passing graph neural network features. For a non-constant null, a generic difference is visible at first order, and a simple motif test attains the aligned order of sample size, suggesting that misalignment is costly mainly for differences that are invisible at low orders. We also give an exactly valid test for one or two graphs per group, at a cost in power. In our simulations, the fitted exponents are close to the predicted ones, and degree-based and random-GNN evaluation metrics stay at their level in a setting where signed triangles need about $65$ graphs.

0.24

Single-Vertex Metropolis on Minor-Free Graphs: A General EPTAS

cs.DS math.CO ·2026-11-17 ·Daniel Skachkov, Yuriy Dorn
theory similarity 0.56
Abstract

We consider a class of combinatorial optimization problems where the goal is to find a largest induced subgraph with a prescribed property. We assume that the property is preserved by taking induced subgraphs and disjoint unions, holds for all edgeless graphs, and can be tested in polynomial time. We study the single-vertex Metropolis process for this class of problems. We show that on graphs excluding an arbitrary fixed minor $H$, this process is a randomized efficient polynomial-time approximation scheme. Starting from any feasible solution on a graph with $n$ vertices, it finds a $(1-\varepsilon)$-approximation within $\exp(O_H(\varepsilon^{-2})) n(n+\log(1/δ))$ steps with probability at least $1-δ$. This includes maximum independent set, maximum induced forest, maximum induced bipartite subgraph, and maximum induced subgraph of degree at most one. The proof uses improving exchanges on one fixed division of the input graph into regions. A recursive separator construction performs each exchange inside a region of size $r$ in at most $2r$ moves, with temporary loss $O_H(\sqrt r)$. We count move sequences through each transition and bound the probability of avoiding all near-optimal states. The general theorem bounds the number of Metropolis steps in terms of the temporary loss along improvement paths. We extend the result to bounded weight imbalance and give a weighted-star obstruction for unrestricted weights.

0.18