← 研踪 PaperTrailarXiv:2610.38998 · v1
How Hard Is It to Compute Cover Time?
首次提交 2026-10-29 06:24
版本更新 2026-10-29 06:24
雷达观测 2026-10-30 11:25
摘要
It is $\#\mathrm{P}\text{-hard}$. Even for connected simple undirected unweighted graphs, deciding whether an expected random-walk cover time is at most a given rational threshold is $\#\mathrm{P}\text{-hard}$ under polynomial-time Turing reductions, both from a specified starting vertex and when maximized over starting vertices. Both families have a universal vertex, called the hub, and diameter two. Deleting the hub leaves a planar bipartite graph, and every non-hub vertex has degree at most five. A shared construction encodes an Euler-tour count in rare covering walks. For specified starts, a number of fractional bits linear in the queried graph's vertex count suffices for recovery. For the maximum-start problem, a fixed cube attachment makes the maximizing starts known, and one interpolation of expected cover times recovers the count. Both reductions use polynomial-size graphs and polynomial-bit threshold queries. For general graphs, both comparison problems can be solved in polynomial time with access to an $\mathrm{NP}^{\mathrm{PP}}$ oracle.
作者备注：29 pages, 4 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-29 06:24 · 最新观测版本
How Hard Is It to Compute Cover Time?
It is $\#\mathrm{P}\text{-hard}$. Even for connected simple undirected unweighted graphs, deciding whether an expected random-walk cover time is at most a given rational threshold is $\#\mathrm{P}\text{-hard}$ under polynomial-time Turing reductions, both from a specified starting vertex and when maximized over starting vertices. Both families have a universal vertex, called the hub, and diameter two. Deleting the hub leaves a planar bipartite graph, and every non-hub vertex has degree at most five. A shared construction encodes an Euler-tour count in rare covering walks. For specified starts, a number of fractional bits linear in the queried graph's vertex count suffices for recovery. For the maximum-start problem, a fixed cube attachment makes the maximizing starts known, and one interpolation of expected cover times recovers the count. Both reductions use polynomial-size graphs and polynomial-bit threshold queries. For general graphs, both comparison problems can be solved in polynomial time with access to an $\mathrm{NP}^{\mathrm{PP}}$ oracle.
查看此版本解读 →查看此版本原文 ↗