Ricerc@Sapienza

A directed multigraph is said vulnerable if it can generate Braess paradox in traffic networks. In this paper, we give a graph–theoretic characterisation of vulnerable directed multigraphs. Analogous results appeared in the literature only for undirected multigraphs and for a specific family of directed multigraphs. The proof of our characterisation provides the first polynomial time algorithm that checks if a general directed multigraph is vulnerable in O(| V| · | E|2). Our algorithm also contributes to the directed subgraph homeomorphism problem without node mapping, by providing another pattern graph for which a polynomial time algorithm exists.