On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

2017/10/12 by Yoichi Iwata, Iwata, Yoichi, Tomoaki Ogasawara +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1710.04376

openalex publication_date 2017/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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'

Citations

• Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
• Data Structures for Weighted Matching and Extensions to b-matching and\n f-factors

Cited by

• Bounding Width on Graph Classes of Constant Diameter

Related

• Linear-Time FPT Algorithms via Network Flow
• Ultimate Polynomial Time
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• The sliding tile puzzle, roots to polynomials, and P vs. NP complexity
• A Nearly Quadratic-Time FPTAS for Knapsack