A graph with forbidden transitions is a pair (G, F_G) where G := (V_g, E_g) is a graph and Fg is a subset of the set {({y, x}, {x, z)) ∈ E~2_G}. A path in a graph with forbidden transitions (G,F_g) is a path in G such that each pair ({y, x}, {x, z}) of consecutive edges does not belong to F_g. It is shown in [S. Szeider, Finding paths in graphs avoiding forbidden transitions, DAM 126] that the problem of deciding the existence of a path between two vertices in a graph with forbidden transitions is N_p-complete. We give an exact exponential time algorithm that decides in time O(2~n ·n~5 -log(n)) whether there exists a path between two vertices of a given n-vertex graph with forbidden transitions. We also investigate a natural extension of the minimum cut problem: we give a polynomial time algorithm that computes a set of forbidden transitions of minimum size that disconnects two given vertices (while in a minimum cut problem we are seeking for a minimum number of edges that disconnect the two vertices). The polynomial time algorithm for that second problem is obtained via a reduction to a standard minimum cut problem in an associated allowed line graph.
展开▼
