有向圖上的回饋點集問題

Abstract

本篇論文的主要內容是在討論有向圖上的回饋點集問題. 對沒有點的入度 數或出度數超過２的有向圖和沒有入度數或出度數超過３的平面有向圖而 言, 回饋點集問題已經被證明是NP-complete.在這篇論文裡, 我們將證 明: 對入度數加出度數的總和不超過３的有向圖和沒有入度數或出度數超 過２的平面有向圖( 或雙分平面有向圖 )而言, 回饋點集問題也是NP- complete.我們也將證明: 對沒有點的入度數加出度數的總和超過２的有 向圖和沒有點的入度數加出度數總和超過３的平面有向圖而言, 回饋點集 問題是存在多項式時間的演算法的. This paper deals with the feedback vertex set ( FVS ) problem for various digraphs. It was proved that the FVS problem is NP- complete for general digraphs and remains NP-complete for digraphs having no in-degree or out-degree exceeding 2, and for planar digraphs having no in-degree or out-degree exceeding 3. In this paper, we shall show that the FVS problem remains NP- complete even for digrpahs in which no vertex has total in- degree and out-degree more than 3, for planar (or planar bipartite) digraphs having no in-degree or out-degree exceeding 2. Moreover, we shall also show that the FVS problem is solvable in polynomial time for digraphs in which no vertex has total in-degree and out-degree more than 2, and for planar digraphs in which no vertex total has total in-degree and out- degree more than 3.