For a fixed graph property $\Phi$ and integer $k \geq 1$, the problem $\#\mathrm{IndSub}(\Phi,k)$ asks to count the induced $k$-vertex subgraphs satisfying $\Phi$ in an input graph $G$. If $\Phi$ is trivial on $k$-vertex graphs (i.e., if $\Phi$ contains either all or no $k$-vertex graphs), this problem is trivial. Otherwise we prove, among other results: - If $\Phi$ is edge-monotone (i.e., closed under deleting edges), then $\#\mathrm{IndSub}(\Phi,k)$ cannot be solved in time $n^{o(k)}$ assuming ETH. This strengthens a result by D\"oring, Marx and Wellnitz [STOC 2024] that only ruled out an exponent of $o(\sqrt{\log k}/ \log \log k)$. Our results also hold when counting modulo fixed primes. - If there is some fixed $\varepsilon > 0$ such that at most $(2-\varepsilon)^{\binom{k}{2}}$ graphs on $k$ vertices satisfy $\Phi$, then $\#\mathrm{IndSub}(\Phi,k)$ cannot be solved in time $n^{o(k/\sqrt{\log k})}$ assuming ETH. Our results hold even when each of the graphs in $\Phi$ may come with an arbitrary individual weight. This generalizes previous results for hereditary properties by Focke and Roth [SIAM J.\ Comput.\ 2024] up to a $\sqrt{\log k}$ factor in the exponent of the lower bound. - If $\Phi$ only depends on the number of edges, then $\#\mathrm{IndSub}(\Phi,k)$ cannot be solved in time $n^{o(k)}$ assuming ETH. This improves on a lower bound by Roth, Schmitt and Wellnitz [FOCS 2020] that only ruled out an exponent of $o(k / \sqrt{\log k})$. In all cases, we also obtain $\mathsf{\#W[1]}$-hardness if $k$ is part of the input and the problem is parameterized by $k$. We also obtain lower bounds on the Weisfeiler-Leman dimension. Our results follow from relatively straightforward Fourier analysis, and our paper subsumes most of the known $\mathsf{\#W[1]}$-hardness results known in the area, often with tighter lower bounds under ETH.


翻译:暂无翻译

0
下载
关闭预览

相关内容

FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【NeurIPS2019】图变换网络:Graph Transformer Network
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日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Transformers in Remote Sensing: A Survey
Arxiv
25+阅读 · 2022年9月2日
Arxiv
69+阅读 · 2022年6月30日
Arxiv
38+阅读 · 2021年8月31日
Anomalous Instance Detection in Deep Learning: A Survey
Arxiv
15+阅读 · 2020年2月6日
UNITER: Learning UNiversal Image-TExt Representations
Arxiv
23+阅读 · 2019年9月25日
VIP会员
相关资讯
【NeurIPS2019】图变换网络:Graph Transformer Network
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日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
相关论文
相关基金
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员