Advances on the List Stubborn Problem

Dantas, S., Faria, L., de Figueiredo, C. M. H., Klein, S., Nogueira, L. T. and Protti, F.

    The 4-partition problem is defined as partitioning the vertex set of a graph G into at most 4 parts A, B, C, D, where each part is not required to be nonempty, and is a stable set, a clique, or has no restriction; and pairs of distinct parts are completely nonadjacent, completely adjacent, or arbitrarily adjacent. The list 4-partition problem generalizes the 4-partition problem by specifying for each vertex x, a list L(x) of parts in which x is allowed to be placed. The only list 4-partition problem not classified as either polynomial time solvable or NP-complete is the list stubborn problem (up to complementarity): A and B are stable sets, D is a clique, each vertex of A is nonadjacent to each vertex of C. We polynomially reduce the general list stubborn instance to a particular instance with a structured graph and only two types of lists. Additionally, we show that this particular list 4-partition problem is polynomially equivalent to a nonlist problem, named twofold stubborn problem.
Cite as: Dantas, S., Faria, L., de Figueiredo, C. M. H., Klein, S., Nogueira, L. T. and Protti, F. (2010). Advances on the List Stubborn Problem. In Proc. 16-th Computing: The Australasian Theory Symposium (CATS 2010) Brisbane, Australia. CRPIT, 109. Viglas, T. and Potanin, A. Eds., ACS. 65-70
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS