On the computational complexity of partial covers of Theta graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Jiř ; í ; Fiala ; Jan Kratochví ; l ; Attila Pó ; r
• 关键词：Computational complexity ; Graph homomorphisms ; Theta graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2008
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：1 April 2008
• 卷：156
• 期：7
• 页码：1143-1149
• 文件大小：185 K

摘要

By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths.