The external constraint 4 nonempty part sandwich problem |
| |
Authors: | Rafael B. Teixeira Simone Dantas |
| |
Affiliation: | a Instituto de Ciências Exatas, Universidade Federal Rural do Rio de Janeiro, Brazilb Instituto de Matemática, Universidade Federal Fluminense, Brazilc COPPE, Universidade Federal do Rio de Janeiro, Brazil |
| |
Abstract: | List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the 2K2-partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the 2K2-partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of 2K2-hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem. |
| |
Keywords: | Graph sandwich problems List partitions Computational complexity Combinatorial algorithms Applied combinatorics |
本文献已被 ScienceDirect 等数据库收录! |