Fixed-parameter tractability of Map-ε\varepsilon-PDD for k+δ+hk+\delta+h

From papers

Let kk, δ\delta, and hh be the parameters of the Map-ε\varepsilon-PDD problem, where hh is the value of HH in a phylogenetic tree. Map-ε\varepsilon-PDD conjecture. Map-ε\varepsilon-PDD is fixed-parameter tractable when parameterized by k+δ+hk+\delta+h. The conjecture is motivated by the known fixed-parameter tractability of ε\varepsilon-PDD with respect to k+hk+h and by the expectation that the corresponding hardness result for Map-1-PDD does not extend to Map-ε\varepsilon-PDD; the proof of the analogous result in the cited work contains an incorrect lemma, so the claim remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Mark Jones and Jannik Schestag, “Parameterized Algorithms for Diversity of Networks with Ecological Dependencies”, arXiv:2510.09512 (2025).

Solutions 0

No solutions have been posted yet.