  We show that the decision problem of recognising whether a triangulated
3-manifold admits a Seifert fibered structure with non-empty boundary is in NP.
We also show that the problem of producing Seifert data for a triangulation of
such a manifold is in the complexity class FNP. We do this by proving that in
any triangulation of a Seifert fibered space with boundary there is both a
fundamental horizontal surface of small degree and a complete collection of
normal vertical annuli whose total weight is bounded by an exponential in the
square of the triangulation size.
