[1710.04376] On the Power of Tree-Depth for Fully Polynomial FPT Algorithmscontact arXivarXiv Twitter

There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty, Fomin et al. (SODA 2017) introduced the concept of fully polynomial FPT algorithms. For a problem with the current best time complexity $O(n^c)$, the goal is to design an algorithm running in $k^{O(1)}n^{c'}$ time for a parameter $k$ and a constant $c'<c$. In this paper, we investigate the complexity of graph problems in P parameterized by tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in $O(\mathrm{td}\cdot m)$ time or $O(\mathrm{td}\cdot (m+n\log n))$ time, where $\mathrm{td}$ is the tree-

1 mentions: @wata_orz
Date: 2020/03/18 11:20

Referring Tweets

@wata_orz 締切は6/1と結構先で、今年のネタはtree-depthというグラフの木っぽさを図る指標の計算です。tree-depthが小さいと負閉路検出とか最大マッチングとかが普段より高速に計算できたりします(t.co/WJ5jUhYGfT)。厳密計算とヒューリスティックの2部門がありマラソン勢には後者が取り組みやすいかも

Related Entries

Read more Invisible Marker: Automatic Annotation of Segmentation Masks for Object Manipulation - YouTube
0 users, 0 mentions 2020/03/10 02:20
Read more GitHub - JetRunner/PABEE: Code for the paper "BERT Loses Patience: Fast and Robust Inference with Ea...
0 users, 0 mentions 2020/06/15 17:21
Read more [2001.07437] Evaluating Weakly Supervised Object Localization Methods Rightopen searchopen navigatio...
0 users, 1 mentions 2020/06/17 18:53
Read more Kaggle Ionコンペ上位解法の(軽い)紹介
0 users, 0 mentions 2020/06/22 14:21
Read more Epidemiological Model for repetitive rapid testing for COVID-19 - Online Technical Discussion Groups...
0 users, 4 mentions 2020/09/16 00:52