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

AUTOR(ES)

Ibrahim, M.S., Maculan, N., Minoux, M.

FONTE

Pesqui. Oper.

DATA DE PUBLICAÇÃO

2014-04

RESUMO

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.

Documentos Relacionados

• A note on the Riemann problem for the random transport equation
• A NOTE ON THE ABSTRACT CAUCHY PROBLEM*
• SOME FURTHER REMARKS ON INEQUALITIES FOR SAMPLE SUMS*
• Transitive functional annotation by shortest-path analysis of gene expression data
• HARDNESS OF THE EYE: AN HISTORICAL NOTE