Generalised dualities and maximal finite antichains in the homomorphism order of relational structures (Q2427538)

The paper characterizes the generalized dualities by showing that these dualities are determined by forbidding homomorphisms from a finite set of forests. In particular, it is shown that, up to homomorphic equivalence, if (\(F, D\)) is a generalized duality, then \(F\) is a set of forests and \(D\) is uniquely determined by \(F\). It also provides the construction of \(D\) from any finite set of forests \(F\). Furthermore, \(F\) is also uniquely determined by a possible right-hand side \(D\). As a result, the paper demonstrates that the decision problem, whether for a finite set \(H\) of graphs, there exists \(F\) such that (\(F, H\)) is a generalized duality, is NP-complete.