(I) We revisit the algorithmic problem of finding all triangles in a graph $G=(V,E)$ with $n$ vertices and $m$ edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in $O(m^{3/2})$ time. We derive this worst-case bound from first principles and with a simple proof. We then provide a combinatorial algorithm for finding all triangles in a graph and show that is amenable to the same running time analysis. We also show that the running time of such an algorithm cannot be improved in the worst-case and for the entire range of parameters $m$ and $n$. Our arguments are extended to the problem of finding all small complete subgraphs of a given fixed size. (II) Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, we present a randomized algorithm that computes a $(1 \pm \varepsilon)$-approximation of the number of triangles in $G$ and finds a witness with high probability in $O\left( n^{\omega(1-\delta)} \right)$ or $O \left( \left( m n^{-2\delta} \right)^{\frac{2\omega}{\omega+1}} \right)$ expected time, provided $G$ has a suitable superlinear number of edges and triangles (where $\omega < 2.376$ is the exponent of matrix multiplication, and $\varepsilon \leq 0.5$, $\delta \leq 0.25$ are positive constants). This limits the range of a conjecture of P\v{a}tra\c{s}cu (2010) regarding the triangle detection problem. (III) We present an algorithm which given a graph $G=(V,E)$ performs one of the following tasks in $O(m+n)$ (i.e., linear) time: (i) compute a $\Omega(1/\sqrt{n})$-approximation of a maximum independent set in $G$ (a well-known NP-hard problem), or (ii) find a triangle in $G$. The run-time is faster than that for any previous method for each of these tasks. A series of trade-off results is also available.


翻译:(I) 我们重新审视在 $G = (V,E) 图形中找到所有三角形的算法问题。 根据 Chiba 和 Nishizeki (1985) 的结果, 可以通过以$(m%3/2}) 时间运行的组合算法来完成这项任务。 我们从最初的原则中得出这个最坏的情况, 并且有一个简单的证明。 我们然后提供一个组合算法, 在一个图形中找到所有三角形, 并且显示可以进行相同的时间分析。 我们还表明, 在最坏的情形下, 以及整个参数范围, 美元 美元 美元 和美元 美元 。 我们的论点可以扩大到找到所有以美元( V, E) 以美元和 美元为单位的正数 。

0
下载
关闭预览

相关内容

【经典书】模式识别导论,561页pdf
专知会员服务
81+阅读 · 2021年6月30日
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
84+阅读 · 2020年12月5日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
已删除
将门创投
6+阅读 · 2019年6月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年6月30日
Arxiv
0+阅读 · 2021年6月30日
VIP会员
相关VIP内容
【经典书】模式识别导论,561页pdf
专知会员服务
81+阅读 · 2021年6月30日
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
84+阅读 · 2020年12月5日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
已删除
将门创投
6+阅读 · 2019年6月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员