数据结构与算法

• 新提交
• 交叉列表
• 替换

查看 最近的 文章

显示 2025年08月26日， 星期二 新的列表

新提交 (展示 6 之 6 条目 )

[1] arXiv:2508.16878 [中文pdf, pdf, html, 其他]

标题： 多项式属性测试 显示英文标题

标题： Polynomial Property Testing

Lior Gishboliner, Asaf Shapira

评论： 综述文章将发表于《计算机科学评论》

主题： 数据结构与算法 (cs.DS) ; 组合数学 (math.CO)

属性测试器是快速的、随机的“选举民意调查”类型算法，用于确定输入（例如图或超图）是否具有某种属性，或者与该属性相差$\varepsilon$。 在密集图模型的属性测试中，已知许多属性可以仅依赖于误差参数$\varepsilon$（而不依赖于输入的大小）进行测试，但当前查询复杂度的界限随着$1/\varepsilon$的函数而迅速增长。 哪些属性可以高效测试，即使用$\mathrm{poly}(1/\varepsilon)$次查询？ 本综述介绍了对此一般问题的现有知识以及一些关键的开放问题。 显示英文摘要

Property testers are fast, randomized "election polling"-type algorithms that determine if an input (e.g., graph or hypergraph) has a certain property or is $\varepsilon$-far from the property. In the dense graph model of property testing, it is known that many properties can be tested with query complexity that depends only on the error parameter $\varepsilon$ (and not on the size of the input), but the current bounds on the query complexity grow extremely quickly as a function of $1/\varepsilon$. Which properties can be tested efficiently, i.e., with $\mathrm{poly}(1/\varepsilon)$ queries? This survey presents the state of knowledge on this general question, as well as some key open problems.

[2] arXiv:2508.17365 [中文pdf, pdf, html, 其他]

标题： 更优的矩形模式匹配索引 显示英文标题

标题： Better Indexing for Rectangular Pattern Matching

Paweł Gawrychowski, Adam Górkiewicz

评论： 论文的扩展版本，将发表于ESA 2025

主题： 数据结构与算法 (cs.DS)

我们重新研究了在给定一个大小为$n$的二维字符串的情况下，构建一个索引结构的复杂性，该结构允许定位大小为$m$的二维模式的所有$k$次出现。 虽然在假设模式为正方形的额外条件下，已知该问题的结构大小为$\mathcal{O}(n)$且查询时间为$\mathcal{O}(m+k)$[Giancarlo, SICOMP 1995]，但一种普遍的观点认为，对于矩形模式，由于对某种自然类方法的一个下界 [Giancarlo, WADS 1993]，无法达到这样的（或甚至类似的）界限。 我们证明，事实上，可以构造一个大小为$\mathcal{O}(n\log n)$的非常简单的结构，该结构对于任何矩形模式在$\mathcal{O}(m+k\log^{\varepsilon}n)$时间内支持此类查询，对于任何$\varepsilon>0$。此外，我们的结构可以在$\tilde{\mathcal{O}}(n)$时间内构造。 显示英文摘要

We revisit the complexity of building, given a two-dimensional string of size $n$, an indexing structure that allows locating all $k$ occurrences of a two-dimensional pattern of size $m$. While a structure of size $\mathcal{O}(n)$ with query time $\mathcal{O}(m+k)$ is known for this problem under the additional assumption that the pattern is a square [Giancarlo, SICOMP 1995], a popular belief was that for rectangular patterns one cannot achieve such (or even similar) bounds, due to a lower bound for a certain natural class of approaches [Giancarlo, WADS 1993]. We show that, in fact, it is possible to construct a very simple structure of size $\mathcal{O}(n\log n)$ that supports such queries for any rectangular pattern in $\mathcal{O}(m+k\log^{\varepsilon}n)$ time, for any $\varepsilon>0$. Further, our structure can be constructed in $\tilde{\mathcal{O}}(n)$ time.

[3] arXiv:2508.17759 [中文pdf, pdf, 其他]

标题： 一点先知能力就足够了 显示英文标题

标题： A Little Clairvoyance Is All You Need

Anupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, Sorrachai Yingchareonthawornchai

主题： 数据结构与算法 (cs.DS)

我们重新审视了在在线设置中，即作业随时间到达时，最小化单机上作业总流程时间的经典问题。长期以来，已知当作业大小事先已知时，最短剩余处理时间（SRPT）算法是最佳的（即$1$-竞争性）[Schrage, 1968]。但在非明察设置中，作业大小仅在作业完成时才被揭示，没有算法可以是常数竞争性的 [Motwani, Phillips, and Torng, 1994]。我们考虑了$\varepsilon$-明察设置，其中$\varepsilon \in [0,1]$，并且每个作业的处理时间一旦其剩余处理时间等于其处理时间的$\varepsilon$分数时就会被揭示。这捕捉了系统用户使用作业处理时间的初始$(1-\varepsilon)$分数来学习其真实长度的设置，然后它可以向算法揭示该信息。该模型由 Yingchareonthawornchai 和 Torng (2017) 提出，并在明察设置（当$\epsilon = 1$时）和非明察设置（当$\varepsilon = 0$时）之间平滑地插值。具体来说，我们是在问：需要多少知识才能绕过这个问题的难度？ 我们证明了一点知识就足够，并且对于每个常数$\varepsilon > 0$都存在一个常数竞争的算法。 更准确地说，对于所有$\varepsilon \in (0,1)$，我们提出一个确定性的$\smash{\lceil \frac{1}{\varepsilon}\rceil}$-竞争算法，这是对确定性算法而言最优的。 我们还为随机算法提出了一个匹配的下界（常数因子以内）。 我们的算法达到这个界限非常简单，并应用了“面对不确定性时的乐观”原则。 证明依赖于在最优队列和算法队列之间保持匹配，并且前缀扩展很小。 显示英文摘要

We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Shortest Remaining Processing Time (SRPT) algorithm is optimal (i.e., $1$-competitive) when the job sizes are known up-front [Schrage, 1968]. But in the non-clairvoyant setting where job sizes are revealed only when the job finishes, no algorithm can be constant-competitive [Motwani, Phillips, and Torng, 1994]. We consider the $\varepsilon$-clairvoyant setting, where $\varepsilon \in [0,1]$, and each job's processing time becomes known once its remaining processing time equals an $\varepsilon$ fraction of its processing time. This captures settings where the system user uses the initial $(1-\varepsilon)$ fraction of a job's processing time to learn its true length, which it can then reveal to the algorithm. The model was proposed by Yingchareonthawornchai and Torng (2017), and it smoothly interpolates between the clairvoyant setting (when $\epsilon = 1$) and the non-clairvoyant setting (when $\varepsilon = 0$). In a concrete sense, we are asking: how much knowledge is required to circumvent the hardness of this problem? We show that a little knowledge is enough, and that a constant competitive algorithm exists for every constant $\varepsilon > 0$. More precisely, for all $\varepsilon \in (0,1)$, we present a deterministic $\smash{\lceil \frac{1}{\varepsilon}\rceil}$-competitive algorithm, which is optimal for deterministic algorithms. We also present a matching lower bound (up to a constant factor) for randomized algorithms. Our algorithm to achieve this bound is remarkably simple and applies the ``optimism in the face of uncertainty'' principle. The proof relies on maintaining a matching between the jobs in the optimum's queue and the algorithm's queue, with small prefix expansion.

[4] arXiv:2508.18017 [中文pdf, pdf, html, 其他]

标题： 面向小集扩张图的常数时间多调用谣言传播 显示英文标题

标题： Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders

Emilio Cruciani, Sebastian Forster, Tijn de Vos

评论： 参加DISC 2025

主题： 数据结构与算法 (cs.DS)

我们研究了经典PUSH&PULL谣言传播过程的一个多调用变体，其中节点在PUSH和PULL操作期间可以联系$k$个邻居，而不是仅一个。 我们证明，通过增加节点之间的通信量，可以使谣言传播更快。 作为一个激励性例子，考虑一个包含$n$个节点的完全图上的过程：虽然标准的PUSH&PULL协议需要$\Theta(\log n)$轮，但我们证明我们的$k$-PUSH&PULL变体以高概率在$\Theta(\log_{k} n)$轮内完成。 我们以一种与扩展敏感的方式推广这一结果，正如对经典PUSH&PULL协议的不同扩展概念（例如，导通性和顶点扩展）所做的那样。 我们考虑小集顶点扩展器，即每个足够小的节点子集都有一个大的邻域的图，确保强大的局部连通性。 特别是，当扩展参数满足$\phi > 1$时，这些图的直径为$o(\log n)$，与其他标准的扩展概念相反。 由于图的直径是谣言传播所需轮数的下限，这使得小集扩展器特别适合快速信息传播。 我们证明，在这些扩展器中，$k$-PUSH&PULL以高概率需要$O(\log_{\phi} n \cdot \log_{k} n)$轮。 我们通过一个简单的下界$\Omega(\log_{\phi} n+ \log_{k} n)$轮来补充这一点。 显示英文摘要

We study a multi-call variant of the classic PUSH&PULL rumor spreading process where nodes can contact $k$ of their neighbors instead of a single one during both PUSH and PULL operations. We show that rumor spreading can be made faster at the cost of an increased amount of communication between the nodes. As a motivating example, consider the process on a complete graph of $n$ nodes: while the standard PUSH&PULL protocol takes $\Theta(\log n)$ rounds, we prove that our $k$-PUSH&PULL variant completes in $\Theta(\log_{k} n)$ rounds, with high probability. We generalize this result in an expansion-sensitive way, as has been done for the classic PUSH&PULL protocol for different notions of expansion, e.g., conductance and vertex expansion. We consider small-set vertex expanders, graphs in which every sufficiently small subset of nodes has a large neighborhood, ensuring strong local connectivity. In particular, when the expansion parameter satisfies $\phi > 1$, these graphs have a diameter of $o(\log n)$, as opposed to other standard notions of expansion. Since the graph's diameter is a lower bound on the number of rounds required for rumor spreading, this makes small-set expanders particularly well-suited for fast information dissemination. We prove that $k$-PUSH&PULL takes $O(\log_{\phi} n \cdot \log_{k} n)$ rounds in these expanders, with high probability. We complement this with a simple lower bound of $\Omega(\log_{\phi} n+ \log_{k} n)$ rounds.

[5] arXiv:2508.18185 [中文pdf, pdf, html, 其他]

标题： 谱反驳在较大域上的半随机$k$-LIN 显示英文标题

标题： Spectral Refutations of Semirandom $k$-LIN over Larger Fields

Nicholas Kocurek, Peter Manohar

主题： 数据结构与算法 (cs.DS)

我们研究强反驳半随机$k$-LIN$(\mathbb{F})$实例的问题：有限域$\mathbb{F}$上的$k$-稀疏非齐次线性方程组。 对于$\mathbb{F} = \mathbb{F}_2$的情况，这是对半随机$k$-XOR 实例进行反驳的广泛研究问题，[GKM22,HKM23] 的工作建立了反驳中的运行时间和子句密度之间的紧密权衡：对于任何参数$\ell$的选择，它们提供了一个$n^{O(\ell)}$-时间算法，以证明在具有$O(n) \cdot \left(\frac{n}{\ell}\right)^{k/2 - 1} \log n /\varepsilon^4$个约束的半随机$k$-XOR 实例中，没有赋值可以满足超过$\frac{1}{2} + \varepsilon$-分数的约束，而 [KMOW17] 的工作提供了良好的证据，表明这在 Sum-of-Squares 层次结构的下界方面是紧密的，最多相差$\mathrm{polylog}(n)$因子。 然而对于更大的域，这个问题的已知结果仅通过将问题归约到$\mathbb{F}_2$的情况来建立，这导致了当前最佳上界和下界之间存在$|{\mathbb{F}}|^{3k}$的差距。 在本文中，我们给出一个算法来反驳半随机$k$-LIN$(\mathbb{F})$实例，并且对域大小$|{\mathbb{F}}|$有“正确”的依赖关系。 对于参数$\ell$的任何选择，我们的算法以$(|{\mathbb{F}}|n)^{O(\ell)}$时间运行，并且可以强反驳具有至少$O(n) \cdot \left(\frac{|{\mathbb{F}^*}| n}{\ell}\right)^{k/2 - 1} \log(n |{\mathbb{F}^*}|) /\varepsilon^4$个约束的半随机$k$-LIN$(\mathbb{F})$实例。我们提供了有力的证据表明，对域大小$|{\mathbb{F}}|$的依赖是最佳的，通过证明一个与该阈值至多相差$\mathrm{polylog}(n |{\mathbb{F}^*}|)$因子的 Sum-of-Squares 层次结构下界。我们的结果还扩展到更一般的有限阿贝尔群的情况。 显示英文摘要

We study the problem of strongly refuting semirandom $k$-LIN$(\mathbb{F})$ instances: systems of $k$-sparse inhomogeneous linear equations over a finite field $\mathbb{F}$. For the case of $\mathbb{F} = \mathbb{F}_2$, this is the well-studied problem of refuting semirandom instances of $k$-XOR, where the works of [GKM22,HKM23] establish a tight trade-off between runtime and clause density for refutation: for any choice of a parameter $\ell$, they give an $n^{O(\ell)}$-time algorithm to certify that there is no assignment that can satisfy more than $\frac{1}{2} + \varepsilon$-fraction of constraints in a semirandom $k$-XOR instance, provided that the instance has $O(n) \cdot \left(\frac{n}{\ell}\right)^{k/2 - 1} \log n /\varepsilon^4$ constraints, and the work of [KMOW17] provides good evidence that this tight up to a $\mathrm{polylog}(n)$ factor via lower bounds for the Sum-of-Squares hierarchy. However for larger fields, the only known results for this problem are established via black-box reductions to the case of $\mathbb{F}_2$, resulting in an $|{\mathbb{F}}|^{3k}$ gap between the current best upper and lower bounds. In this paper, we give an algorithm for refuting semirandom $k$-LIN$(\mathbb{F})$ instances with the "correct" dependence on the field size $|{\mathbb{F}}|$. For any choice of a parameter $\ell$, our algorithm runs in $(|{\mathbb{F}}|n)^{O(\ell)}$-time and strongly refutes semirandom $k$-LIN$(\mathbb{F})$ instances with at least $O(n) \cdot \left(\frac{|{\mathbb{F}^*}| n}{\ell}\right)^{k/2 - 1} \log(n |{\mathbb{F}^*}|) /\varepsilon^4$ constraints. We give good evidence that this dependence on the field size $|{\mathbb{F}}|$ is optimal by proving a lower bound for the Sum-of-Squares hierarchy that matches this threshold up to a $\mathrm{polylog}(n |{\mathbb{F}^*}|)$ factor. Our results also extend to the more general case of finite Abelian groups.

[6] arXiv:2508.18256 [中文pdf, pdf, html, 其他]

标题： 精确优化最小支配集 显示英文标题

标题： Exact Optimization for Minimum Dominating Sets

Enqiang Zhu, Qiqi Bao, Yu Zhang, Pu Wu, Chanjuan Liu

主题： 数据结构与算法 (cs.DS)

最小支配集（MDS）问题是一个广为人知的组合优化问题，具有许多实际应用。 其NP难的性质使得随着图的规模增大，获取精确解变得越来越困难。 本文介绍了ParDS，一种在分支限界框架内解决MDS问题的精确算法。 ParDS具有两个关键创新：一种先进的线性规划技术，能够产生更紧的下界，以及一组新的约简规则，在求解过程中动态简化实例。 与IJCAI 2023和2024会议上提出的领先精确算法相比，ParDS在理论上表现出更优的下界质量。 在标准基准数据集上的实验结果突显了ParDS的几个显著优势：它在70%的图类别中达到最快的求解时间，特别是在大型稀疏图上，最快单个实例的速度提升了高达3,411倍，并成功解决了其他算法在5小时时间限制内无法解决的43个实例中的16个。 这些发现确立了ParDS作为精确求解MDS问题的最先进解决方案。 显示英文摘要

The Minimum Dominating Set (MDS) problem is a well-established combinatorial optimization problem with numerous real-world applications. Its NP-hard nature makes it increasingly difficult to obtain exact solutions as the graph size grows. This paper introduces ParDS, an exact algorithm developed to address the MDS problem within the branch-and-bound framework. ParDS features two key innovations: an advanced linear programming technique that yields tighter lower bounds and a set of novel reduction rules that dynamically simplify instances throughout the solving process. Compared to the leading exact algorithms presented at IJCAI 2023 and 2024, ParDS demonstrates theoretically superior lower-bound quality. Experimental results on standard benchmark datasets highlight several significant advantages of ParDS: it achieves fastest solving times in 70% of graph categories, especially on large, sparse graphs, delivers a speed-up of up to 3,411 times on the fastest individual instance, and successfully solves 16 out of 43 instances that other algorithms were unable to resolve within the 5-hour time limit. These findings establish ParDS as a state-of-the-art solution for exactly solving the MDS problem.

交叉提交 (展示 2 之 2 条目 )

[7] arXiv:2508.17349 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 2层扇平面性在多项式时间内 显示英文标题

标题： 2-Layer Fan-Planarity in Polynomial Time

Yasuaki Kobayashi, Yuto Okada

评论： 7页，4图

主题： 计算几何 (cs.CG) ; 数据结构与算法 (cs.DS)

在本文中，我们给出一个多项式时间算法，用于判断输入的二分图是否允许存在一个2层扇形平面绘制，解决了自2015年以来多个论文中提出的一个开放问题。 显示英文摘要

In this paper, we give a polynomial-time algorithm for deciding whether an input bipartite graph admits a 2-layer fan-planar drawing, resolving an open problem posed in several papers since 2015.

[8] arXiv:2508.18104 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 关于Grundy支配和零 forcing问题的参数化复杂性 显示英文标题

标题： On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems

Robert Scheffler

主题： 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 数据结构与算法 (cs.DS) ; 组合数学 (math.CO)

我们考虑两种不同的问题族，这些问题涉及图中的支配。 一方面，我们关注支配序列。 在这样的序列中，每个顶点支配图中未被序列中任何先前顶点支配的某个顶点。 寻找最长支配序列的问题被称为$\mathsf{Grundy~Domination}$。 根据使用闭邻域还是开邻域进行支配，该问题有另外三种版本。 我们证明，当以解的大小为参数时，这四个问题变体都是$\mathsf{W[1]}$-hard。 另一方面，我们考虑零强制问题族，这些问题是Grundy支配问题的参数化对偶。 在这些问题中，人们寻找最初被染成蓝色的最小顶点集，使得某些颜色变化规则能够将所有其他顶点染成蓝色。 Bhyravarapu 等人 [IWOCA 2025] 表明，其中一个问题，称为$\mathsf{Zero~Forcing~Set}$，当以树宽或解的大小为参数时属于$\mathsf{FPT}$。 我们将他们的树宽结果扩展到零强制的其他三种变体及其相应的Grundy支配问题。 我们的算法还意味着一个$\mathsf{FPT}$算法用于$\mathsf{Grundy~Domination}$，当以不在支配序列中的顶点数量为参数时。 显示英文摘要

We consider two different problem families that deal with domination in graphs. On the one hand, we focus on dominating sequences. In such a sequence, every vertex dominates some vertex of the graph that was not dominated by any earlier vertex in the sequence. The problem of finding the longest dominating sequence is known as $\mathsf{Grundy~Domination}$. Depending on whether the closed or the open neighborhoods are used for domination, there are three other versions of this problem. We show that all four problem variants are $\mathsf{W[1]}$-hard when parameterized by the solution size. On the other hand, we consider the family of Zero forcing problems which form the parameterized duals of the Grundy domination problems. In these problems, one looks for the smallest set of vertices initially colored blue such that certain color change rules are able to color all other vertices blue. Bhyravarapu et al. [IWOCA 2025] showed that one of these problems, known as $\mathsf{Zero~Forcing~Set}$, is in $\mathsf{FPT}$ when parameterized by the treewidth or the solution size. We extend their treewidth result to the other three variants of zero forcing and their respective Grundy domination problems. Our algorithm also implies an $\mathsf{FPT}$ algorithm for $\mathsf{Grundy~Domination}$ when parameterized by the number of vertices that are not in the dominating sequence.

替换提交 (展示 9 之 9 条目 )

[9] arXiv:2309.11175 (替换) [中文pdf, pdf, html, 其他]

标题： 流中的测试频率分布 显示英文标题

标题： Testing frequency distributions in a stream

Claire Mathieu, Michel de Rougemont

评论： 28页，4图

主题： 数据结构与算法 (cs.DS)

我们研究当观察到来自包含$n$个不同项目的宇宙的$N$数据项流时，如何验证特定的频率分布。 我们引入\emph{相对弗雷歇距离}来以一种统一的方式比较两个频率函数。 我们考虑两种流模型：仅插入和滑动窗口。 我们为某一类函数提供了一个测试器，当给出$f$并且$g$由一个流定义时，该测试器可以以高概率判断$f $是否接近$g$或者$f$是否远离$g$。 如果$f$是均匀的，我们证明一个空间$\Omega(n)$下界。 如果$f$减少得足够快，那么我们仅使用空间$O(\log^2 n\cdot \log\log n)$。 分析依赖于 Spacesaving 算法\cite{MAE2005,Z22}和对流的采样。 显示英文摘要

We study how to verify specific frequency distributions when we observe a stream of $N$ data items taken from a universe of $n$ distinct items. We introduce the \emph{relative Fr\'echet distance} to compare two frequency functions in a homogeneous manner. We consider two streaming models: insertions only and sliding windows. We present a Tester for a certain class of functions, which decides if $f $ is close to $g$ or if $f$ is far from $g$ with high probability, when $f$ is given and $g$ is defined by a stream. If $f$ is uniform we show a space $\Omega(n)$ lower bound. If $f$ decreases fast enough, we then only use space $O(\log^2 n\cdot \log\log n)$. The analysis relies on the Spacesaving algorithm \cite{MAE2005,Z22} and on sampling the stream.

[10] arXiv:2310.04236 (替换) [中文pdf, pdf, 其他]

标题： 带有模式避免输入的优化 显示英文标题

标题： Optimization with pattern-avoiding input

Benjamin Aram Berendsohn, László Kozma, Michal Opler

评论： 许可证已更新

主题： 数据结构与算法 (cs.DS) ; 组合数学 (math.CO)

排列模式避免是枚举和极值组合学中的核心概念。 在动态最优性猜想的背景下（Sleator，Tarjan，STOC 1983），Chalermsook，Goswami，Kozma，Mehlhorn 和 Saranurak（FOCS 2015）猜想，当搜索序列是模式避免时，最优二叉搜索树（BST）的摊销搜索成本是常数。 迄今为止最好的界限是$2^{\alpha{(n)}(1+o(1))}$，最近由 Chalermsook，Pettie 和 Yingchareonthawornchai（SODA 2024）获得；其中$n$是 BST 的大小，$\alpha(\cdot)$是反阿克曼函数。 在本文中，我们解决了该猜想，证明了一个紧致的$O(1)$界。 这表明了动态最优性的一个障碍：任何候选的在线 BST（例如，splay 树或贪婪树）必须达到这个最优值，但目前的分析技术只能给出超常数的界限。 更广泛地说，我们认为模式避免输入的易处理性是一种普遍现象，不仅限于 BST 或甚至数据结构。 为了说明这一点，我们表明当输入避免任意一个固定的、事先未知的模式时，可以从单位区间中高效计算出一个$k$服务器解决方案，处理$n$个请求，总成本为$n^{O(1/\log k)}$，与最坏情况下的$\Theta(n/k)$界相比；以及从单位方块中处理$n$个点的旅行商路线，长度为$O(\log{n})$，与最坏情况下的$\Theta(\sqrt{n})$界相比；欧几里得最小生成树、Steiner 树和最近邻图也有类似的结果。 我们证明这两个结果都是紧致的。 我们的技术建立在 Marcus-Tardos 对 Stanley-Wilf 猜想的证明之上，并基于最近出现的 twin-width 概念。 显示英文摘要

Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. In this paper we study the effect of permutation pattern-avoidance on the complexity of optimization problems. In the context of the dynamic optimality conjecture (Sleator, Tarjan, STOC 1983), Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak (FOCS 2015) conjectured that the amortized search cost of an optimal binary search tree (BST) is constant whenever the search sequence is pattern-avoiding. The best known bound to date is $2^{\alpha{(n)}(1+o(1))}$ recently obtained by Chalermsook, Pettie, and Yingchareonthawornchai (SODA 2024); here $n$ is the BST size and $\alpha(\cdot)$ the inverse-Ackermann function. In this paper we resolve the conjecture, showing a tight $O(1)$ bound. This indicates a barrier to dynamic optimality: any candidate online BST (e.g., splay trees or greedy trees) must match this optimum, but current analysis techniques only give superconstant bounds. More broadly, we argue that the easiness of pattern-avoiding input is a general phenomenon, not limited to BSTs or even to data structures. To illustrate this, we show that when the input avoids an arbitrary, fixed, a priori unknown pattern, one can efficiently compute a $k$-server solution of $n$ requests from a unit interval, with total cost $n^{O(1/\log k)}$, in contrast to the worst-case $\Theta(n/k)$ bound; and a traveling salesman tour of $n$ points from a unit box, of length $O(\log{n})$, in contrast to the worst-case $\Theta(\sqrt{n})$ bound; similar results hold for the euclidean minimum spanning tree, Steiner tree, and nearest-neighbor graphs. We show both results to be tight. Our techniques build on the Marcus-Tardos proof of the Stanley-Wilf conjecture, and on the recently emerging concept of twin-width.

[11] arXiv:2409.10575 (替换) [中文pdf, pdf, html, 其他]

标题： 基于优先级的稳定匹配问题局部搜索算法 显示英文标题

标题： A Tie-breaking based Local Search Algorithm for Stable Matching Problems

Junyuan Qiu

评论： 提交至《启发式算法期刊》

主题： 数据结构与算法 (cs.DS) ; 人工智能 (cs.AI) ; 离散数学 (cs.DM) ; 优化与控制 (math.OC)

稳定婚姻问题中的不完整列表和绑定（SMTI）以及带有绑定的医院/居民问题（HRT）在匹配理论中具有重要意义，并有广泛的实际应用。 在本文中，我们引入了一种基于绑定打破的局部搜索（TBLS）算法，旨在为SMTI和HRT问题实现最大规模的弱稳定匹配。 TBLS首先任意解决所有绑定，并通过根据偏好等级和当前稳定匹配调整绑定内的相对顺序来迭代地改进绑定打破策略。 此外，我们引入了TBLS-E，这是针对SMTI问题的一个注重公平性的TBLS变体。 该变体保持最大化匹配规模的目标，同时通过两个简单的修改增强公平性。 与另外十种近似和局部搜索算法相比，TBLS实现了最高的匹配规模，而TBLS-E表现出最低的性别平等成本。 显著的是，TBLS-E保持了与TBLS相当的匹配规模。 我们的两种算法在解决大规模实例时都比其他局部搜索算法具有更快的计算速度。 此外，我们的可扩展性分析表明，随着问题规模的增加，两种算法都能保持高效的性能。 显示英文摘要

The stable marriage problem with incomplete lists and ties (SMTI) and the hospitals/residents problem with ties (HRT) are important in matching theory with broad practical applications. In this paper, we introduce a tie-breaking based local search (TBLS) algorithm designed to achieve a weakly stable matching of maximum size for both the SMTI and HRT problems. TBLS begins by arbitrarily resolving all ties and iteratively refines the tie-breaking strategy by adjusting the relative order within ties based on preference ranks and the current stable matching. Additionally, we introduce TBLS-E, an equity-focused variant of TBLS, specifically designed for the SMTI problem. This variant maintains the objective of maximizing matching size, while enhancing equity through two simple modifications. In comparison with ten other approximation and local search algorithms, TBLS achieves the highest matching size, while TBLS-E exhibits the lowest sex equality cost. Significantly, TBLS-E preserves a matching size comparable to that of TBLS. Both our algorithms demonstrate faster computational speed than other local search algorithms in solving large-scale instances. Moreover, our scalability analysis shows that both algorithms maintain efficient performance as problem size increases.

[12] arXiv:2503.09762 (替换) [中文pdf, pdf, html, 其他]

标题： 通过状态无关策略实现动态匹配的常数遗憾 显示英文标题

标题： Achieving constant regret for dynamic matching via state-independent policies

Süleyman Kerimov, Pengyu Qian, Mingwei Yang, Sophie H. Yu

主题： 数据结构与算法 (cs.DS) ; 优化与控制 (math.OC) ; 概率 (math.PR)

我们研究一个具有有限代理类型集中式离散时间动态双向匹配模型。代理随机地随时间到达，并加入其类型专用队列等待匹配。我们关注状态无关的贪心策略，这些策略通过仅根据跨类型的代理可用性做出匹配决策，而不是需要完整的队列长度信息，在所有时间点都能实现常数遗憾。这种策略在生命拯救应用如肾脏交换中特别有吸引力，因为与状态相关策略相比，它们需要更少的信息并提供更多的透明度。首先，对于无环匹配网络，我们分析了Kerimov等人[2023]提出的一种确定性优先级策略，该策略在匹配上遵循静态优先级顺序。我们推导了第一个关于一般位置差距（GPG）参数$\epsilon$的显式遗憾界限，该参数衡量流体松弛远离退化性的距离。其次，对于一般的双向匹配网络，我们设计了一种随机的状态无关贪心策略，该策略以最优尺度$O(\epsilon^{-1})$实现常数遗憾，与Kerimov等人[2024]建立的现有下限相匹配。 显示英文摘要

We study a centralized discrete-time dynamic two-way matching model with finitely many agent types. Agents arrive stochastically over time and join their type-dedicated queues waiting to be matched. We focus on state-independent greedy policies that achieve constant regret at all times by making matching decisions based solely on agent availability across types, rather than requiring complete queue-length information. Such policies are particularly appealing for life-saving applications such as kidney exchange, as they require less information and provide more transparency compared to state-dependent policies. First, for acyclic matching networks, we analyze a deterministic priority policy proposed by Kerimov et al. [2023] that follows a static priority order over matches. We derive the first explicit regret bound in terms of the general position gap (GPG) parameter $\epsilon$, which measures the distance of the fluid relaxation from degeneracy. Second, for general two-way matching networks, we design a randomized state-independent greedy policy that achieves constant regret with optimal scaling $O(\epsilon^{-1})$, matching the existing lower bound established by Kerimov et al. [2024].

[13] arXiv:2507.04473 (替换) [中文pdf, pdf, html, 其他]

标题： 通过分解技术的切割相对生存网络设计的紧致保证 显示英文标题

标题： Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique

Nikhil Kumar, JJ Nan, Chaitanya Swamy

主题： 数据结构与算法 (cs.DS)

在经典的\emph{可生存网络设计问题}（SNDP）中，我们给定一个无向图$G = (V, E)$，非负的边成本，以及一些$(s_i,t_i,r_i)$元组，其中$s_i,t_i\in V$和$r_i\in\mathbb{Z}_+$。 我们寻求一个最小成本的子集$H \subseteq E$，使得即使任何$r_i-1$条边失效，每个$s_i$-$t_i$对仍保持连通。 众所周知，SNDP可以使用一个弱超模的\emph{切割需求函数} $f$进行等价建模，其中我们寻求一个包含至少$f(S)$条边的最小成本边集，这些边跨越每一个割$S \subseteq V$。 最近，Dinitz等人 提出了一种SNDP的变体，该变体相对于$G$强制实现了\emph{相对的}级别的容错能力，目标是找到一个至少与$G$本身同样容错的解决方案$H$。他们通过路径和故障集来形式化这一点，从而产生了\emph{路径相对 SNDP}。 沿着这一思路，我们引入了一种相对网络设计的新模型，称为\emph{相对切割SNDP}（CR-SNDP），其中目标是选择一个最小成本的边子集，以尽可能最大程度地满足给定的（弱超模）割需求函数，即通过在每个割上选取$\min\{f(S),|\delta_G(S)|\}$条边$S\subseteq V$。 与SNDP不同，SNDP的割相对版本和路径相对版本并不等价。 CR-SNDP（以及路径相对SNDP）得到的割需求函数不是弱超模的，自然LP松弛的极点解不一定对应于一组紧密的割约束的层叠族。 因此，不能直接使用标准技术来为此问题设计近似算法。 我们开发了一种\emph{新分解技术}来克服这一困难，并用它给出了\emph{紧的$2$-近似算法 for CR-SNDP}。 我们还展示了这些相对SNDP问题的新难解性结果。 显示英文摘要

In the classical \emph{survivable-network-design problem} (SNDP), we are given an undirected graph $G = (V, E)$, non-negative edge costs, and some $(s_i,t_i,r_i)$ tuples, where $s_i,t_i\in V$ and $r_i\in\mathbb{Z}_+$. We seek a minimum-cost subset $H \subseteq E$ such that each $s_i$-$t_i$ pair remains connected even if any $r_i-1$ edges fail. It is well-known that SNDP can be equivalently modeled using a weakly-supermodular \emph{cut-requirement function} $f$, where we seek a minimum-cost edge-set containing at least $f(S)$ edges across every cut $S \subseteq V$. Recently, Dinitz et al. proposed a variant of SNDP that enforces a \emph{relative} level of fault tolerance with respect to $G$, where the goal is to find a solution $H$ that is at least as fault-tolerant as $G$ itself. They formalize this in terms of paths and fault-sets, which gives rise to \emph{path-relative SNDP}. Along these lines, we introduce a new model of relative network design, called \emph{cut-relative SNDP} (CR-SNDP), where the goal is to select a minimum-cost subset of edges that satisfies the given (weakly-supermodular) cut-requirement function to the maximum extent possible, i.e., by picking $\min\{f(S),|\delta_G(S)|\}$ edges across every cut $S\subseteq V$. Unlike SNDP, the cut-relative and path-relative versions of SNDP are not equivalent. The resulting cut-requirement function for CR-SNDP (as also path-relative SNDP) is not weakly supermodular, and extreme-point solutions to the natural LP-relaxation need not correspond to a laminar family of tight cut constraints. Consequently, standard techniques cannot be used directly to design approximation algorithms for this problem. We develop a \emph{novel decomposition technique} to circumvent this difficulty and use it to give a \emph{tight $2$-approximation algorithm for CR-SNDP}. We also show new hardness results for these relative-SNDP problems.

[14] arXiv:2504.19582 (替换) [中文pdf, pdf, html, 其他]

标题： 忠实的泛图对于子式闭包类 显示英文标题

标题： Faithful universal graphs for minor-closed classes

Paul Bastide, Louis Esperet, Carla Groenland, Claire Hilaire, Clément Rambaud, Alexandra Wesolek

评论： 36页，8张图，许多参考文献。v3：当通用图包含所有平面图时，主要结果成立（而不是v2中的所有环面图）

主题： 组合数学 (math.CO) ; 数据结构与算法 (cs.DS)

由Huynh、Mohar、Šámal、Thomassen和Wood在2021年证明，任何包含每个可数平面图作为子图的可数图都有无限团小结构。我们证明了这个结果的有限定量版本：对于固定的$t$，如果图$G$是$K_t$-小结构自由的，并且包含每个$n$顶点平面图作为子图，那么$G$有$2^{\Omega(n)}$个顶点。 另一方面，我们构造了一个多项式大小的$K_4$-不含子图的图，其中包含每个$n$-顶点树作为诱导子图，并且构造了一个多项式大小的$K_7$-不含子图的图，其中包含每个$n$-顶点$K_4$-不含子图的图作为诱导子图。 这回答了Bergold、Iršič、Lauff、Orthaber、Scheucher和Wesolek最近提出的一些问题。 我们更广泛地研究了各种类别的通用图的阶数（有界度、树深度、路径宽度或树宽的图），如果通用图保留了原始类的一些结构。 显示英文摘要

It was proved by Huynh, Mohar, \v{S}\'amal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We prove a finite, quantitative version of this result: for fixed $t$, if a graph $G$ is $K_t$-minor-free and contains every $n$-vertex planar graph as a subgraph, then $G$ has $2^{\Omega(n)}$ vertices. On the other hand, we construct a polynomial size $K_4$-minor-free graph containing every $n$-vertex tree as an induced subgraph, and a polynomial size $K_7$-minor-free graph containing every $n$-vertex $K_4$-minor-free graph as induced subgraph. This answers several problems raised recently by Bergold, Ir\v{s}i\v{c}, Lauff, Orthaber, Scheucher and Wesolek. We study more generally the order of universal graphs for various classes (of graphs of bounded degree, treedepth, pathwidth, or treewidth), if the universal graphs retain some of the structure of the original class.

[15] arXiv:2507.19417 (替换) [中文pdf, pdf, html, 其他]

标题： 通过熵的规则图的循环因子 显示英文标题

标题： Cycle-factors of regular graphs via entropy

Micha Christoph, Nemanja Draganić, António Girão, Eoin Hurley, Lukas Michel, Alp Müyesser

评论： 9页。一篇被接受到FOCS 2025的论文的扩展版本，包含开放问题

主题： 组合数学 (math.CO) ; 离散数学 (cs.DM) ; 数据结构与算法 (cs.DS) ; 概率 (math.PR)

一个随机排列的$n$个元素，平均大约有$\log n$个循环。我们将其推广到所有$d$-正则图在$n$个顶点上，通过证明这样的图的随机环因子平均有$\mathcal{O}((n\log d)/d)$个循环。这在常数因子范围内是紧致的，并改进了Vishnoi提出的形如$\mathcal{O}(n/\sqrt{\log d})$的最佳先前界限。我们的结果还产生了寻找这样的环因子以及在图连通时寻找长度为$(1+\mathcal{O}((\log d)/d)) \cdot n$的巡回路线的随机多项式时间算法。这推进了Magnant和Martin的猜想以及Vishnoi、Feige、Ravi和Singh研究的问题。我们的证明使用了熵的语言，以利用正则二分图中完美匹配数的上下界非常接近这一事实。 显示英文摘要

It is a classical result that a random permutation of $n$ elements has, on average, about $\log n$ cycles. We generalise this fact to all directed $d$-regular graphs on $n$ vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}(n/\sqrt{\log d})$ due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1+\mathcal{O}((\log d)/d)) \cdot n$ if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close.

[16] arXiv:2508.14831 (替换) [中文pdf, pdf, html, 其他]

标题： $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$通过树高压缩 显示英文标题

标题： $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression

Logan Nye

评论： 33页

主题： 计算复杂性 (cs.CC) ; 人工智能 (cs.AI) ; 数据结构与算法 (cs.DS)

我们证明了确定性多带图灵机的平方根空间模拟，表明 $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ \emph{以磁带单元在固定有限字母表上测量}。 关键步骤是一个高度压缩定理，它统一地（并在对数空间内）将一个块尊重运行的规范左深简洁计算树重新塑造为一个二叉树，其在任何深度优先搜索路径上的评估栈深度为 $O(\log T)$ 对于 $T=\lceil t/b\rceil$，同时保留 $O(b)$ 在叶节点处的工作空间和 $O(1)$ 在内部节点处的。 Edges have \emph{地址/拓扑} checkable in $O(\log t)$ space, and \emph{语义} correctness across merges is witnessed by an exact $O(b)$ bounded-window replay at the unique interface. Algorithmically, an Algebraic Replay Engine with constant-degree maps over a constant-size field, together with pointerless DFS and index-free streaming, ensures constant-size per-level tokens and eliminates wide counters, yielding the additive tradeoff $S(b)=O(b+t/b)$. Choosing $b=\Theta(\sqrt{t})$ gives $O(\sqrt{t})$ space with no residual multiplicative polylog factors. The construction is uniform, relativizes, and is robust to standard model choices. 后果包括针对大小为$s$有界扇入电路的分支程序上界$2^{O(\sqrt{s})}$，通过标准层次论证对$\mathrm{SPACE}[n]$完全问题的紧致二次时间下界，以及$O(\sqrt{t})$空间验证解释器；在显式局部性假设下，该框架扩展到几何$d$维模型。 从概念上讲，这项工作将路径跟踪作为$O(\sqrt{t})$的主要障碍，并通过每路径分析而不是易受阻碍的技术进行结构高度压缩来消除它。 显示英文摘要

We prove a square-root space simulation for deterministic multitape Turing machines, showing $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ \emph{measured in tape cells over a fixed finite alphabet}. The key step is a Height Compression Theorem that uniformly (and in logspace) reshapes the canonical left-deep succinct computation tree for a block-respecting run into a binary tree whose evaluation-stack depth along any DFS path is $O(\log T)$ for $T=\lceil t/b\rceil$, while preserving $O(b)$ workspace at leaves and $O(1)$ at internal nodes. Edges have \emph{addressing/topology} checkable in $O(\log t)$ space, and \emph{semantic} correctness across merges is witnessed by an exact $O(b)$ bounded-window replay at the unique interface. Algorithmically, an Algebraic Replay Engine with constant-degree maps over a constant-size field, together with pointerless DFS and index-free streaming, ensures constant-size per-level tokens and eliminates wide counters, yielding the additive tradeoff $S(b)=O(b+t/b)$. Choosing $b=\Theta(\sqrt{t})$ gives $O(\sqrt{t})$ space with no residual multiplicative polylog factors. The construction is uniform, relativizes, and is robust to standard model choices. Consequences include branching-program upper bounds $2^{O(\sqrt{s})}$ for size-$s$ bounded-fan-in circuits, tightened quadratic-time lower bounds for $\mathrm{SPACE}[n]$-complete problems via the standard hierarchy argument, and $O(\sqrt{t})$-space certifying interpreters; under explicit locality assumptions, the framework extends to geometric $d$-dimensional models. Conceptually, the work isolates path bookkeeping as the chief obstruction to $O(\sqrt{t})$ and removes it via structural height compression with per-path analysis rather than barrier-prone techniques.

[17] arXiv:2508.15323 (替换) [中文pdf, pdf, html, 其他]

标题： 费米子到费米子低密度奇偶校验码 显示英文标题

标题： Fermion-to-Fermion Low-Density Parity-Check Codes

Chong-Yuan Xu, Ze-Chuan Liu, Yong Xu

评论： 21页（包括补充材料），11幅图。此版本更正了一些拼写错误

主题： 量子物理 (quant-ph) ; 数据结构与算法 (cs.DS)

在基于量子比特的量子计算机上模拟费米子系统通常需要大量的计算资源，这是由于需要将费米子映射到量子比特。因此，设计一种直接使用费米子的容错量子计算机为解决这一挑战提供了一种有效方案。在这里，我们介绍了一种利用费米子到费米子低密度奇偶校验（LDPC）码进行容错费米子量子计算的协议。我们的方法使用了一个费米子LDPC存储器，将其状态转移到费米子颜色码处理器中，随后在这些处理器上执行逻辑操作。我们提出使用奇权重逻辑马约拉纳算符来形成码空间，作为费米子LDPC码的存储器，并提供一个识别这些逻辑算符的算法。我们给出了示例，表明费米子码的编码率通常与量子比特码相匹配，而逻辑错误率可以显著低于物理错误率。此外，我们提出了两种用于执行费米子格手术的方法，以促进状态转移。最后，我们使用我们的协议模拟了费米子系统的动态，展示了有效的误差抑制。 显示英文摘要

Simulating fermionic systems on qubit-based quantum computers often demands significant computational resources due to the requirement to map fermions to qubits. Thus, designing a fault-tolerant quantum computer that operates directly with fermions offers an effective solution to this challenge. Here, we introduce a protocol for fault-tolerant fermionic quantum computation utilizing fermion-to-fermion low-density parity-check (LDPC) codes. Our method employs a fermionic LDPC memory, which transfers its state to fermionic color code processors, where logical operations are subsequently performed. We propose using odd-weight logical Majorana operators to form the code space, serving as memory for the fermionic LDPC code, and provide an algorithm to identify these logical operators. We present examples showing that the coding rate of fermionic codes often matches that of qubit codes, while the logical error rate can be significantly lower than the physical error rate. Furthermore, we propose two methods for performing fermionic lattice surgery to facilitate state transfer. Finally, we simulate the dynamics of a fermionic system using our protocol, illustrating effective error suppression.