09511 Open Problems - Parameterized complexity and approximation algorithms

Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx

This document is a collection of open problems presented at a Dagstuhl seminar on Parameterized Complexity and Approximation Algorithms. It's not a single research paper with a unified methodology and results, but rather a snapshot of the field's frontiers in late 2009, highlighting challenges and potential research directions. Therefore, some sections like "Methods," "Datasets," and "Key Results" will be "Not discussed in the paper" as they don't apply to a collection of open problems.

TL;DR

This document presents a collection of open problems from a 2009 Dagstuhl seminar, spanning areas like parameterized complexity, approximation algorithms, and their intersections. These problems highlight fundamental challenges in understanding the computational limits of various problems, particularly concerning efficiency when parameterized by specific problem characteristics.

What Problem Does This Paper Address?

The core "problem" addressed by this document is the identification and articulation of significant open questions in the fields of parameterized complexity and approximation algorithms. These are not problems with a single, defined solution, but rather challenging research directions that researchers believe are crucial for advancing the understanding of computational complexity. The document aims to stimulate research by clearly stating these challenges, providing context, and hinting at potential approaches or related work. The problems touch upon areas like:

  • The limits of efficient computation: Can certain problems be solved significantly faster than brute-force if we focus on specific parameters (e.g., the size of a clique, the number of colors)? This relates to the Exponential Time Hypothesis (ETH) and its implications.
  • Bridging theory and practice: How can theoretical advancements in parameterized complexity be made more practical, especially for large-scale problems?
  • Understanding the relationship between different complexity classes: For instance, exploring equivalences between assumptions about SAT solving time and fixed-parameter tractability.
  • Developing new algorithmic paradigms: Investigating novel ways to design algorithms, such as "effectivization" of mathematical implications or finding better parameters for existing problems.

Methods

Not discussed in the paper. This document is a collection of open problems, not a research paper detailing specific methodologies.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The pervasive influence of the Exponential Time Hypothesis (ETH): Many problems discussed rely on or aim to prove lower bounds based on the ETH, suggesting its central role in understanding the limits of parameterized algorithms.
  • The quest for "tight" bounds: Researchers are actively seeking to prove that existing algorithms for problems like k-clique or k-SUM are indeed optimal up to polynomial factors, often by relating them to strong complexity assumptions.
  • The challenge of "sparsification": A key technical hurdle in some reductions is the need to avoid or overcome the "sparsification lemma," indicating a need for new proof techniques.
  • The potential of "effectivization": The idea of transforming mathematical implications about parameters into efficient algorithms is presented as a powerful tool for algorithm design, with potential for both theoretical and practical impact.
  • The difficulty of finding "good" parameters: For some problems, like cluster editing, the standard parameterization might not be the most useful in practice, motivating the search for alternative, more "practical" parameters.
  • The ongoing debate about subexponential algorithms: For several NP-hard problems, the question of whether subexponential fixed-parameter algorithms exist (especially for planar or H-minor-free graphs) remains a significant open area.
  • The connection between parameterized complexity and approximation: The document highlights the interplay between finding exact parameterized solutions and developing approximation algorithms, particularly in the context of W-hard problems.

Key Results

Not discussed in the paper. This document lists open problems, not solved results.

Limitations and Future Work

  • The inherent nature of open problems: The primary "limitation" is that these are unsolved challenges. The document implicitly points to future work by posing these questions.
  • Specific areas for future research include:
    • Proving tight lower bounds for problems like k-clique and k-SUM under strong complexity assumptions.
  • Developing new techniques to avoid the sparsification lemma in reductions.
  • Investigating the equivalence between different complexity assumptions (e.g., CNF SAT vs. k-SAT complexity).
  • Finding efficient "effectivizations" for mathematical implications between parameters, and exploring lower bounds for such effectivizations.
  • Determining the parameterized complexity of problems like metric dimension and compatible coloring.
  • Closing the gap between upper and lower bounds for EPTASs on planar graphs.
  • Developing fixed-parameter approximation algorithms for problems like Disjoint Paths and Periodic Scheduling.
  • Finding more practical parameterizations for problems like cluster editing.
  • Exploring subexponential fixed-parameter algorithms for problems like k-Steiner tree and Subset Feedback Vertex Set.
  • Formalizing a standard notion of Fixed-Parameter Approximation (FPA) reduction.
  • Investigating the parameterized complexity of counting lattice points in bounded polytopes.
  • Developing fixed-parameter algorithms for weighted graph problems with less dependence on weights.
  • Understanding the parameterized complexity of making graphs distance-balanced.

Summary updated

Abstract

The paper contains a list of the problems presented on Monday, December 14, 2009 at the open problem session of the Seminar on Parameterized Complexity and Approximation Algorithms, held at Schloss Dagstuhl in Wadern, Germany.
BibTeX
@inproceedings{demaine2009open,
  author = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Dániel Marx},
  title = {{09511 Open Problems - Parameterized complexity and approximation algorithms}},
  booktitle = {Parameterized Complexity and Approximation Algorithms},
  year = {2009},
  url = {https://openreview.net/forum?id=nIz5z1Z_nYq},
}
Figure