Chain Minors are FPT
Jarosław Błasiok, Marcin Kamiński · Algorithmica · 2016
Given two finite partially ordered sets P and Q, we say that P is a chain minor of Q if there exists a partial function f from the elements of Q to the elements of P such that for every chain in P there is a chain $$C_Q$$ in Q with the property that f restricted to $$C_Q$$ is an isomorphism of chains C and $$C_Q$$ . We give an algorithm to decide whether a partially ordered set P is a chain minor of a partially ordered set Q, which runs in time $${\mathcal {O}}\left( |Q| \log |Q|\right) $$ for every fixed partially ordered set P. This solves an open problem from the monograph by Downey and Fellows (Parameterized complexity. Springer, New York, 1999) who asked whether the problem was fixed parameter tractable.