The complexity of the extendibility problem for finite posets
by
Laszlo Zadori
USz Bolyai Institute, Szeged, Hungary

For a finite poset R let EXT(R) stand for the following problem: Suppose Q is a finite poset and f is a partial map from Q to R. Decide whether there exists a fully defined monotone extension of f from Q to R.

It is easy to see that EXT(R) is in the class NP. In 1997 Pratt and Tiuryn proved that EXT(R) is NP-complete if R is a crown. It is not too hard to show that the problem is in P if R admits a near unanimity operation. Pratt and Tiuryn also gave examples of a poset R which admits no near unanimity operation and yet EXT(R) is in P.

In the talk I sketch my results obtained recently on the complexity of EXT(R). It turns out that for posets admitting totally symmetric idempotent operations of any arity the problem is in P. The proof of that is of course based on an algorithm. (By a result of Larose the class of finite posets admitting totally symmetric idempotent operations of any arity is wider then the class of finite posets admitting a near unanimity operation.) Moreover, for any poset R admitting no nontrivial idempotent operations EXT(R) is NP-complete, which is a generalization of Pratts' result on crowns. My conjecture is that if R admits no totally symmetric idempotent operations then EXT(R) is NP-complete.

Date received: May 10, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caee-29.