Inapproximability results related to monophonic convexity

详细信息    查看全文

• 作者：Eurinardo R. Costa^a ; ^{eurinardo@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Mitre C. Dourado^b ; ^{mitre@nce.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Rudini M. Sampaio^a ; ^{rudinims@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; ^{rudini@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Monophonic convexity ; Bipartite graphs ; NP-completeness ; Inapproximability ; Convexity number ; Percolation time
• 刊名：Discrete Applied Mathematics
• 出版年：2015
• 出版时间：31 December 2015
• 年：2015
• 卷：197
• 期：Complete
• 页码：70-74
• 全文大小：470 K

文摘

In 2010, it was proved that the interval number and the convexity number on the monophonic convexity are NP-hard on general graphs (Dourado et al., 2010). In this paper, we extend this results on the monophonic convexity. We prove that deciding if the interval number is at most 2 and deciding if the percolation time is at most 1 are NP-complete problems even in bipartite graphs. We also prove that the convexity number is as hard to approximate as the maximum clique problem. Finally, we obtain polynomial time algorithms to determine the convexity number on hereditary graph classes such that the computation of the clique number is polynomial time solvable (as perfect graphs and planar graphs).