检索结果-内蒙古大学图书馆

Universality of the matching number in percolated regular graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Diskin, Sahar Kang, Mihyun Lichev, Lyuben School of Mathematical Sciences Tel Aviv University Tel Aviv6997801 Israel Institute of Discrete Mathematics Graz University of Technology Graz8010 Austria Institute of Statistics and Mathematical Methods in Economics Technical University of Vienna ViennaA-1040 Austria

Fix a sequence of d-regular graphs (Gd)d∈N and denote by Gd,p the graph obtained from Gd after edge-percolation with probability p = c/d, for a constant c > 0. We prove a quantitative local convergence of (Gd,p)d∈N. In combination with results of Bordenave, Lelarge and Salez, it implies that the rescaled matching number of Gd,p is asymptotically equivalent to that of the binomial random graph G(n, c/n). © 2025, CC BY.

关键词： graph algorithms

Internal Incoherency Scores for Constraint-based Causal Discovery algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Faltenbacher, Sofia Wahl, Jonas Herman, Rebecca Runge, Jakob Technical University Dresden Germany Germany

Causal discovery aims to infer causal graphs from observational or experimental data. Methods such as the popular PC algorithm are based on conditional independence testing and utilize enabling assumptions, such as the faithfulness assumption, for their inferences. In practice, these assumptions, as well as the functional assumptions inherited from the chosen conditional independence test, are typically taken as a given and not further tested for their validity on the data. In this work, we propose internal coherency scores that allow testing for assumption violations and finite sample errors, whenever detectable without requiring ground truth or further statistical tests. We provide a complete classification of erroneous results, including a distinction between detectable and undetectable errors, and prove that the detectable erroneous results can be measured by our scores. We illustrate our coherency scores on the PC algorithm with simulated and real-world datasets, and envision that testing for internal coherency can become a standard tool in applying constraint-based methods, much like a suite of tests is used to validate the assumptions of classical regression analysis. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

FLIP graphS WITH SYMMETRY AND NEW MATRIX MULTIPLICATION SCHEMES

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Moosbauer, Jakob Poole, Michael Department of Computer Science University of Warwick Coventry United Kingdom United Kingdom

The flip graph algorithm is a method for discovering new matrix multiplication schemes by following random walks on a graph. We introduce a version of the flip graph algorithm for matrix multiplication schemes that admit certain symmetries. This significantly reduces the size of the search space, allowing for more efficient exploration of the flip graph. The symmetry in the resulting schemes also facilitates the process of lifting solutions from F2 to Z. Our results are new schemes for multiplying 5×5 matrices using 93 multiplications and 6×6 matrices using 153 multiplications over arbitrary ground fields. © 2025, CC BY.

关键词： graph algorithms

Parameterised algorithms for temporal reconfiguration problems

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Davot, Tom Enright, Jessica Larios-Jones, Laura Univ Angers LERIA SFR MATHSTIC AngersF-49000 France School of Computing Science University of Glasgow United Kingdom

Given a static vertex-selection problem (e.g. independent set, dominating set) on a graph, we can define a corresponding temporal reconfiguration problem on a temporal graph which asks for a sequence of solutions to the vertex-selection problem at each time such that we can reconfigure from one solution to the next. We can think of each solution in the sequence as a set of vertices with tokens placed on them;our reconfiguration model allows us to slide tokens along active edges of a temporal graph. We show that it is possible to efficiently check whether one solution can be reconfigured to another, and show that approximation results on the static vertex-selection problem can be adapted with a lifetime factor to the reconfiguration version. Our main contributions are fixed-parameter tractable algorithms with respect to: enumeration time of the related static problem;the combination of temporal neighbourhood diversity and lifetime of the input graph;and the combination of lifetime and treewidth of the footprint graph. © 2025, CC BY.

关键词： graph algorithms

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Blikstad, Joakim Jiang, Yonggang Mukhopadhyay, Sagnik Yingchareonthawornchai, Sorrachai CWI the Netherlands & KTH Sweden MPI-INF & Saarland University Germany University of Birmingham United Kingdom ETH Zürich Switzerland The Hebrew University Israel

A recent breakthrough by [LNPSY STOC’21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequential model. This raises a natural question: What is the relationship between s-t and global vertex connectivity in other computational models? In this paper, we demonstrate that the connection between global and s-t variants behaves very differently across computational models: • In parallel and distributed models, we obtain almost tight reductions from global to s-t vertex connectivity. In PRAM, this leads to a nω+o(1)-work and no(1)-depth algorithm for vertex connectivity, improving over the 35-year-old Õ(nω+1)-work O(log2 n)-depth algorithm by [LLW FOCS’86], where ω is the matrix multiplication exponent and n is the number of vertices. In CONGEST, the reduction implies the first sublinear-round (when the diameter is moderately small) vertex connectivity algorithm. This answers an open question in [JM STOC’23]. • In contrast, we show that global vertex connectivity is strictly harder than s-t vertex connectivity in the two-party communication setting, requiring Θe （n1.5） bits of communication. The s-t variant was known to be solvable in Õ(n) communication [BvdBEMN FOCS’22]. Our results resolve open problems raised by [MN STOC’20, BvdBEMN FOCS’22, AS SOSA’23]. At the heart of our results is a new graph decomposition framework we call common-neighborhood clustering, which can be applied in multiple models. Finally, we observe that global vertex connectivity cannot be solved without using s-t vertex connectivity by proving an s-t to global reduction in dense graphs in the PRAM and communication models. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

DISPERSION IS (ALMOST) OPTIMAL UNDER (A)SYNCHRONY

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Kshemkalyani, Ajay D. Kumar, Manish Molla, Anisur Rahaman Sharma, Gokarna University of Illinois Chicago United States IIT Madras India Indian Statistical Institute Kolkata India Kent State University United States

The dispersion problem has received much attention recently in the distributed computing literature. In this problem, k ≤ n agents placed initially arbitrarily on the nodes of an n-node, m-edge anonymous graph of maximum degree ∆ have to reposition autonomously to reach a configuration in which each agent is on a distinct node of the graph. Dispersion is interesting as well as important due to its connections to many fundamental coordination problems by mobile agents on graphs, such as exploration, scattering, load balancing, relocation of self-driven electric cars (robots) to recharge stations (nodes), etc. The objective has been to provide a solution that optimizes simultaneously time and memory complexities. There exist graphs for which the lower bound on time complexity is Ω(k). Memory complexity is Ω(log k) per agent independent of graph topology. The state-of-the-art algorithms have (i) time complexity O(k log2 k) and memory complexity O(log(k + ∆)) under the synchronous setting [DISC’24] and (ii) time complexity O(min{m, k∆}) and memory complexity O(log(k + ∆)) under the asynchronous setting [OPODIS’21]. In this paper, we improve substantially on this state-of-the-art. Under the synchronous setting as in [DISC’24], we present the first optimal O(k) time algorithm keeping memory complexity O(log(k + ∆)). Under the asynchronous setting as in [OPODIS’21], we present the first algorithm with time complexity O(k log k) keeping memory complexity O(log(k + ∆)), which is time-optimal within an O(log k) factor despite asynchrony. Both results were obtained through novel techniques to quickly find empty nodes to settle agents, which may be of independent interest. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

Water transport on finite graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Vilkas, Timo Statistiska Institutionen Ekonomihögskolan vid Lunds Universitet Lund220 07 Sweden

Consider a simple finite graph and its nodes to represent identical water barrels (containing different amounts of water) on a level plane. Each edge corresponds to a (locked, water-filled) pipe connecting two barrels below the plane. We fix one node v and consider the optimization problem relating to the maximum value to which the level in v can be raised without pumps, i.e. by opening/closing pipes in a suitable order. This fairly natural optimization problem originated from the analysis of an opinion formation process and proved to be not only sufficiently intricate in order to be of independent interest, but also difficult from an algorithmic point of *** Codes 05C35, 05C85, 91A68 © 2025, CC BY.

关键词： graph algorithms

Novel Complexity Results for Temporal Separators with Deadlines

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Dondi, Riccardo Lafond, Manuel Università degli Studi di Bergamo Italy Université de Sherbrooke Canada

We consider two variants, (s,z,)-Temporal Separator and (s,z,)-Temporal Cut, respectively, of the vertex separator and the edge cut problem in temporal graphs. The goal is to remove the minimum number of vertices (temporal edges, respectively) in order to delete all the temporal paths that have time travel at most between a source vertex s and target vertex z. First, we solve an open problem in the literature showing that (s,z,)-Temporal Separator is NP-complete even when the underlying graph has pathwidth bounded by four. We complement this result showing that (s,z,)-Temporal Separator can be solved in polynomial time for graphs of pathwidth bounded by three. Then we consider the approximability of (s,z,)-Temporal Separator and we show that it cannot be approximated within factor 2Ω(log1−Ε |V |) for any constant Ε > 0, unless NP ⊆ ZPP (V is the vertex set of the input temporal graph) and that the strict version is approximable within factor − 1 (we show also that it is unliklely that this factor can be improved). Then we consider the (s,z,)-Temporal Cut problem, we show that it is APX-hard and we present a 2 log2(2) approximation algorithm. © 2025, CC BY.

关键词： graph algorithms

Detecting Arbitrary Planted Subgraphs in Random graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Elimelech, Dor Huleihel, Wasim School of Electrical Engineering and Computer Engineering Tel Aviv University Tel Aviv6997801 Israel

The problems of detecting and recovering planted structures/subgraphs in ErdősRényi random graphs, have received significant attention over the past three decades, leading to many exciting results and mathematical techniques. However, prior work has largely focused on specific ad hoc planted structures and inferential settings, while a general theory has remained elusive. In this paper, we bridge this gap by investigating the detection of an arbitrary planted subgraph Γ = Γn in an Erdős-Rényi random graph G(n, qn), where the edge probability within Γ is pn. We examine both the statistical and computational aspects of this problem and establish the following results. In the dense regime, where the edge probabilities pn and qn are fixed, we tightly characterize the information-theoretic and computational thresholds for detecting Γ, and provide conditions under which a computational-statistical gap arises. Most notably, these thresholds depend on Γ only through its number of edges, maximum degree, and maximum subgraph density. Our lower and upper bounds are general and apply to any value of pn and qn as functions of n. Accordingly, we also analyze the sparse regime where qn = Θ(n−α) and pn − qn = Θ(qn), with α ∈ [0, 2], as well as the critical regime where pn = 1 − o(1) and qn = Θ(n−α), both of which have been widely studied, for specific choices of Γ. For these regimes, we show that our bounds are tight for all planted subgraphs investigated in the literature thus far—and many more. Finally, we identify conditions under which detection undergoes sharp phase transition, where the boundaries at which algorithms succeed or fail shift abruptly as a function of qn © 2025, CC BY.

关键词： graph algorithms