Thumbnail

On the complexity of the Eulerian closed walk with precedence path constraints problem

Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha (2012), On the complexity of the Eulerian closed walk with precedence path constraints problem, Theoretical Computer Science, 439, p. 16-29. 10.1016/j.tcs.2012.03.014

View/Open
Type
Article accepté pour publication ou publié
Date
2012
Journal name
Theoretical Computer Science
Volume
439
Publisher
Elsevier
Pages
16-29
Publication identifier
Metadata
Show full item record
Author(s)
Kerivin, Hervé

Lacroix, Mathieu cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
The Eulerian closed walk problem in a digraph is a well-known polynomial-time solvable problem. In this paper, we show that if we impose the feasible solutions to fulfill some precedence constraints specified by paths of the digraph, then the problem becomes NP-complete. We also present a polynomial-time algorithm to solve this variant of the Eulerian closed walk problem when the set of paths does not contain some forbidden structure. This allows us to give necessary and sufficient conditions for the existence of feasible solutions in this polynomial-time solvable case.
Subjects / Keywords
Eulerian closed walk; Precedence path constraints; NP-completeness; Polynomial-time algorithm