01

FPT Algorithms and Tree Decompositions

Chapter 1 • Advanced

120 min

FPT Algorithms and Tree Decompositions

Fixed-Parameter Tractability (FPT)

Problems solvable in O(f(k) · n^c) where:

  • k is parameter
  • f is arbitrary function
  • c is constant

Example: Vertex Cover

python.js
def vertex_cover_fpt(graph, k):
    """FPT algorithm for Vertex Cover"""
    if k == 0:
        return len(graph) == 0
    
    if len(graph) == 0:
        return True
    
    # Pick edge (u, v)
    u, v = next(iter(graph.items()))
    
    # Either u or v in cover
    return (vertex_cover_fpt(remove_vertex(graph, u), k - 1) or
            vertex_cover_fpt(remove_vertex(graph, v), k - 1))

Tree Decomposition

Decompose graph into tree structure.

Practice Problems

  1. FPT algorithms for NP-hard problems
  2. Tree decomposition
  3. Dynamic programming on treewidth
Next
Approximation Algorithms

Related Tutorials