首页 | 本学科首页   官方微博 | 高级检索  
     


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, Brazil
  • b Instituto de Matemática, Universidade Federal Fluminense, Brazil
  • c 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 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

    Copyright©北京勤云科技发展有限公司  京ICP备09084417号