一句话：将UCQ枚举的可处理性障碍归约到不平衡三角形检测，并给出两自连接自由CQ并的二分性。
本文研究合取查询并（UCQ）答案枚举能否达到线性预处理与常数延迟，旨在找出已知 free-connex union extension 之外是否还有可处理 UCQ。作者利用 3SUM 假设及 3SUM 到图三角形列举的归约，证明部分未分类 UCQ 困难；进而指出顶点不平衡三分图三角形检测是分类所有自连接自由 UCQ 时无法回避的问题，并证明其困难性与某族 UCQ 等价。若该检测问题答案为否定，则得到两个自连接自由 CQ 之并的二分定理。结论将该枚举复杂度障碍定位为单一决策问题：不突破不平衡三角形检测，就无法为更多两自连接自由 CQ 并找到高效算法；反之，足够高效的检测算法可转化为该类 UCQ 的算法。
We study the enumeration of answers to Unions of Conjunctive Queries (UCQs) with optimal time guarantees. More precisely, we wish to identify the queries that can be solved with linear preprocessing time and constant delay. Despite the basic nature of this problem, it was shown only recently that UCQs can be solved within these time bounds if they admit free-connex union extensions, even if all individual CQs in the union are intractable with respect to the same complexity measure. Our goal is to understand whether there exist additional tractable UCQs, not covered by the currently known algorithms. As a first step, we show that some previously unclassified UCQs are hard using the classic 3SUM hypothesis, via a known reduction from 3SUM to triangle listing in graphs. As a second step, we identify a question about a variant of this graph task that is unavoidable if we want to classify all self-join-free UCQs: is it possible to decide the existence of a triangle in a vertex-unbalanced tripartite graph in linear time? We prove that this task is equivalent in hardness to some family of UCQs. Finally, we show a dichotomy for unions of two self-join-free CQs if we assume the answer to this question is negative. In conclusion, this paper pinpoints a computational barrier in the form of a single decision problem that is key to advancing our understanding of the enumeration complexity of many UCQs. Without a breakthrough for unbalanced triangle detection, we have no hope of finding an efficient algorithm for additional unions of two self-join-free CQs. On the other hand, a sufficiently efficient unbalanced triangle detection algorithm can be turned into an efficient algorithm for a family of UCQs currently not known to be tractable.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2210-11996,
title = {Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries},
author = {Karl Bringmann and Nofar Carmeli},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 1},
year = {2025},
doi = {10.46298/lmcs-21(1:29)2025}
}