A note on the NP-hardness of the separation problem on some valid inequalities for the elementary shortest path problem

Pesquisa Operacional

M.s. Ibrahim²  N. Maculan¹  M. Minoux¹ 

[1] ,Université A. Moumoun Faculté des Sciences Niamey,Niger

关键词: polytope;    digraphs;    shortest path;    valid inequality;    separation;   

DOI  :  10.1590/S0101-74382014000100009

来源: SciELO

【 摘 要 】

In this paper, we investigate the separation problem on some valid inequalities for the s - t elementary shortest path problem in digraphs containing negative directed cycles. As we will see, these inequalities depend to a given parameter k ∈ ℕ. To show the NP-hardness of the separation problem of these valid inequalities, considering the parameter k ∈ ℕ, we establish a polynomial reduction from the problem of the existence of k + 2 vertex-disjoint paths between k + 2 pairs of vertices (s1, t1), (s2, t2) ... (sk+2, t k+2) in a digraph to the decision problem associated to the separation of these valid inequalities. Through some illustrative instances, we exhibit the evoked polynomial reduction in the cases k = 0 and k = 1.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License