论文标题
最糟糕的扩展案例减少
Worst-Case to Expander-Case Reductions
论文作者
论文摘要
近年来，使用扩展器分解方法来开发许多图形算法，从而导致长期复杂性障碍的重大改善。这种强大的锤子使社区（1）认为，在最差的图表上，大多数问题与在扩展器上一样容易，并且（2）怀疑扩张器分解是打破剩余的长期障碍，以细粒度的复杂性打破剩余的长期障碍。 我们着手研究这两件事是真实的程度（以及哪些问题）。为此，我们提出了最糟糕的案例概念来扩展自我还原。我们为基本图形问题设计了此类减少的集合，为他们验证了信念（1）。该列表包括$ k $ -clique，$ 4 $循环，最大基数匹配，顶点覆盖和最小主导套件。有趣的是，对于大多数（但不是全部）这些问题，证明是通过简单的小工具减少而不是通过扩张器分解来证明，这表明这种锤子实际上是对问题和矛盾的无用（2）。
In recent years, the expander decomposition method was used to develop many graph algorithms, resulting in major improvements to longstanding complexity barriers. This powerful hammer has led the community to (1) believe that most problems are as easy on worst-case graphs as they are on expanders, and (2) suspect that expander decompositions are the key to breaking the remaining longstanding barriers in fine-grained complexity. We set out to investigate the extent to which these two things are true (and for which problems). Towards this end, we put forth the concept of worst-case to expander-case self-reductions. We design a collection of such reductions for fundamental graph problems, verifying belief (1) for them. The list includes $k$-Clique, $4$-Cycle, Maximum Cardinality Matching, Vertex-Cover, and Minimum Dominating Set. Interestingly, for most (but not all) of these problems the proof is via a simple gadget reduction, not via expander decompositions, showing that this hammer is effectively useless against the problem and contradicting (2).
