A Directed Path Family is a family of subsets of some finite ground set whose members call be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G Such that each word ill the language is the set of arcs of some path in G, is a polynomial-time solvable problem. (C) 2009 Elsevier B.V. All rights reserved.
On the complexity of recognizing directed path families / N., Apollonio; Franciosa, Paolo Giulio. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 157:11(2009), pp. 2525-2535. [10.1016/j.dam.2009.03.006]
On the complexity of recognizing directed path families
FRANCIOSA, Paolo Giulio
2009
Abstract
A Directed Path Family is a family of subsets of some finite ground set whose members call be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G Such that each word ill the language is the set of arcs of some path in G, is a polynomial-time solvable problem. (C) 2009 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
