Given an undirected graph $G=(V,E)$ and an integer $\ell$, the Eccentricity Shortest Path (ESP) asks to find a shortest path $P$ such that for every vertex $v\in V(G)$, there is a vertex $w\in P$ such that $d_G(v,w)\leq \ell$, where $d_G(v,w)$ represents the distance between $v$ and $w$ in $G$. Dragan and Leitert [Theor. Comput. Sci. 2017] showed that the optimization version of this problem, which asks to find the minimum $\ell$ for the ESP problem, is NP-hard even on planar bipartite graphs with maximum degree 3. They also showed that ESP is W[2]-hard when parameterized by $\ell$. On the positive side, Ku\v cera and Such\'y [IWOCA 2021] showed that the problem exhibits fixed parameter tractable (FPT) behavior when parameterized by modular width, cluster vertex deletion set, maximum leaf number, or the combined parameters disjoint paths deletion set and $\ell$. It was asked as an open question in the above paper, if ESP is FPT parameterized by disjoint paths deletion set or feedback vertex set. We answer these questions partially and obtain the following results: - ESP is FPT when parameterized by disjoint paths deletion set, split vertex deletion set or the combined parameters feedback vertex set and eccentricity of the graph. - We design a $(1+\epsilon)$-factor FPT approximation algorithm when parameterized by the feedback vertex set number. - ESP is W[2]-hard when parameterized by the chordal vertex deletion set.


翻译:基于参数的偏心最短路径问题的算法 给定一个无向图G = (V,E)和整数l,偏心最短路径(ESP)问题要求找到一条最短路径P,使得对于每个顶点v∈V(G),存在一个顶点w∈P,使得d_G(v,w) ≤ l,其中d_G(v,w)表示G中v和w之间的距离。Dragan和Leitert [Theor. Comput. Sci. 2017]证明了该问题的最优化版本,该版本要求找到ESP问题的最小l,即使在最大度为3的平面二分图上,该问题也是NP难的。他们还表明,当参数为l时,ESP是W[2]-hard的。积极的方面是,Ku\v cera和Such\'y [IWOCA 2021]表明,该问题的参数化宽度与支配集、最大叶数或联合参数不相交的路径删除集和l存在固定参数跨越特性(FPT)。在上述论文中提出了以下问题,即如果将ESP参数化为不相交的路径删除集或反馈顶点集,是否可以FPT。我们部分回答了这些问题,获得了以下结果:-当将不相交的路径删除集、分割顶点删除集或联合参数反馈顶点集和图的偏心率参数化时,ESP是FPT的;-当将反馈顶点集数量参数化时,我们设计了一个$(1+\epsilon)$-近似FPT算法;-当将和弦顶点删除集参数化时,ESP是W[2]-hard的。

0
下载
关闭预览

相关内容

FPT:International Conference on Field-Programmable Technology。 Explanation:现场可编程技术国际会议。 Publisher:IEEE。 SIT: http://dblp.uni-trier.de/db/conf/fpt/
【硬核书】图:理论与算法,394页pdf
专知会员服务
86+阅读 · 2023年1月28日
专知会员服务
31+阅读 · 2021年7月15日
【NeurIPS2020】点针图网络,Pointer Graph Networks
专知会员服务
39+阅读 · 2020年9月27日
专知会员服务
123+阅读 · 2020年9月8日
八篇NeurIPS 2019【图神经网络(GNN)】相关论文
专知会员服务
43+阅读 · 2020年1月10日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
图神经网络库PyTorch geometric
图与推荐
17+阅读 · 2020年3月22日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
Arxiv
0+阅读 · 2023年5月19日
Arxiv
11+阅读 · 2022年9月1日
VIP会员
相关VIP内容
【硬核书】图:理论与算法,394页pdf
专知会员服务
86+阅读 · 2023年1月28日
专知会员服务
31+阅读 · 2021年7月15日
【NeurIPS2020】点针图网络,Pointer Graph Networks
专知会员服务
39+阅读 · 2020年9月27日
专知会员服务
123+阅读 · 2020年9月8日
八篇NeurIPS 2019【图神经网络(GNN)】相关论文
专知会员服务
43+阅读 · 2020年1月10日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
图神经网络库PyTorch geometric
图与推荐
17+阅读 · 2020年3月22日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
Top
微信扫码咨询专知VIP会员