Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most $(1+\epsilon)n$ edges (where $n$ is the number of vertices and $\epsilon$ is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge $e$ belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of $e$. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general bounded-degree graphs, the query complexity of any such algorithm must be $\Omega(\sqrt{n})$. This lower bound holds for constant-degree graphs that have high expansion. Next we design an algorithm for (bounded-degree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence non-expanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is $poly(1/\epsilon, h)$ (independent of $n$ and the maximum degree), where $h$ is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a high-level there are several similarities, and we highlight both the similarities and the differences.


翻译:构造图树的图形是图形理论中最基本的任务之一。 我们考虑在设置本地算法时, 这个问题的宽松版本。 放松的是, 构建的子图是一个分散的子图, 最多包含$(1 ⁇ ⁇ epsilon) n 的边缘( 美元是脊椎数, $\\ epsilon$ 是给定的近似/ 差分参数 ) 。 在当地设置中, 目标是快速确定给定的边缘 $ / 美元是否属于这样的子图( $1 / 美元 / 美元 / 美元 / / 美元 / 美元) 。 目标在于快速确定给定的边端是否属于这样的子值, 而不是构建整个子线 。 我们设计了一个( 方向 ) ( 水平 ) 本地值 / 美元 的直径直值, 最高值 和 最高值 值 值 。 因此, 不同的 算算算出一个小数 。 。 。 我们设计了一个不同的 。

0
下载
关闭预览

相关内容

专知会员服务
42+阅读 · 2020年12月18日
专知会员服务
50+阅读 · 2020年12月14日
斯坦福EE364a《凸优化》课件,301页ppt
专知会员服务
95+阅读 · 2020年7月14日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
AAAI2020 图相关论文集
图与推荐
10+阅读 · 2020年7月15日
通俗易懂!《图机器学习导论》附69页PPT
专知
55+阅读 · 2019年12月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Arxiv
0+阅读 · 2021年6月15日
Arxiv
0+阅读 · 2021年6月14日
Arxiv
0+阅读 · 2021年6月14日
Arxiv
0+阅读 · 2021年6月12日
Arxiv
0+阅读 · 2021年6月10日
VIP会员
相关资讯
AAAI2020 图相关论文集
图与推荐
10+阅读 · 2020年7月15日
通俗易懂!《图机器学习导论》附69页PPT
专知
55+阅读 · 2019年12月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Top
微信扫码咨询专知VIP会员