Braessパラドックスとは，各辺にコスト関数を備え，出発地と目的地を表す2点s,tが指定されたグラフG上で，辺の追加がナッシュフローのコストを増加させる好ましくない現象である．この現象の有無を判定する問題は一般にNP完全であることが知られている．本稿では，グラフGとs,tを入力とし，どのようなコスト関数でもBraessパラドックスが起こり得ないか否かを判定する問題を考える．この問題はGが無向の場合は過去の結果を直接利用することで多項式時間で解ける．本稿では，Gが有向の場合にはこのアプローチがNP困難となるステップを含むことを示し，別のアルゴリズムによって多項式時間で解けることを示す．