Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

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