In this paper we show that the problem of finding a chordless path between a vertex s and a vertex t containing a vertex v remains NP-complete in bipartite graphs, thereby strengthening the previous results on the same problem. We show a relation between this problem and two interval operators: the simple path interval operator in hypergraphs and the even-chorded path interval operator in graphs. We show that the problem of computing the two mentioned intervals is NP-complete.
Mezzini, M. (2010). On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs. THEORETICAL COMPUTER SCIENCE, 411(7-9), 1212-1220 [10.1016/j.tcs.2009.12.017].
On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
MEZZINI, MAURO
2010-01-01
Abstract
In this paper we show that the problem of finding a chordless path between a vertex s and a vertex t containing a vertex v remains NP-complete in bipartite graphs, thereby strengthening the previous results on the same problem. We show a relation between this problem and two interval operators: the simple path interval operator in hypergraphs and the even-chorded path interval operator in graphs. We show that the problem of computing the two mentioned intervals is NP-complete.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
