マトロイド的特性に関する点除去問題のプライマル・デュアル法による近似

• 藤戸 敏弘

  広島大学工学部 第二類(電気系)回路システム工学講座

書誌事項

タイトル別名

• A Primal-Dual Approximation of Node-Deletion Problems for Matroidal Properties

抄録

本稿は、グラフの遺伝的特性に関する点除去問題に対する多項式時間近似可能性について論じる。そのような点除去問題は一般にNP-困難であるが、極小禁止グラフが有限個しか存在しない特性の場合、最小値の高々ある定数倍の値をもつ近似解が効率良く求められることが知られている.これに対し、極小禁止郭グラフが無限個存在する場合は、帰還点集合問題を唯一の例外として、そのような多項式時間アルゴリズムは知られていない.ここでは、どのようなグラフの辺集合の上でも定義できるようなマトロイドによって導入される遺伝的特性に着目する。まず初めに、そのような特性に関する点除去問題全てが一様に、簡単かつ新しい整数計画として定式化されることを示す。そして、この整数計画ならびにその線形計画緩和の双対から、そのよつな点除去問題全てに対するプライマル・デュアル近似アルゴリズムを設計する.このアルゴリズムを解析し、保証できる近似比の一般式を与える。次に、このブライマル・デュアル近似アプローチの応用の一つとして、帰還点集合問題が唯一の例外ではないことを示す.即ち,極小禁止グラフを無限個もちながら、対応する点除去問題において近似比2の解力勤率良く計算できるような遺伝的が他にも、しかも無限掴存在することを示す。グラフのマトロイダル・ファミリーという概念とその定義の緩和から、そのようなグラフ特性を導く.しかも、そのような特性の無限列は、点被覆問題や帰還点集合問題におけるグラフ特性の一般化となっている。
This paper is concerned with polynomial time approximability of node-deletion problems for hereditary properties. It has been known that when such a property has only a finite number of minimal forbidden graphs the corresponding node-deletion problem can be efficiently approximated to within some constant factor of the optimum. On the other hand when there exist infinitely many minimal forbidden graphs no constant factor approximation has been known except for the case of the Feedback Vertex Set(FVS) problem in undirected graphs. We will focus our attention to such properties that are derived from matroids definable on the edge set of any graphs. It will be shown first that all the node-deletion problem for such properties can be uniformly formulated by a simple but non-standard form of the integer programming. The primal-dual approximation algorithm for all such problems is then presented based on this and the dual of its linear programming relaxation. The performance ratios implied by this approach will be analyzed and given in a general form. We will show next, as an application of the primal-dual approach to the node-deletion problems, that the FVS problem is not the sole exceptional case; i.e., there exist other graph (hereditary) properties with an infinite number of minimal forbidden graphs, for which the node-deletion problems are efficiently approximable to within a factor of 2. In fact, we will show, there are infinitely many of them. Such properties are derived from the notion of matroidal families of graphs and relaxing the definitions for them. It will be observed at the same time that an infinite sequence of such properties is constituted with those for both Vertex Cover and FVS problems at its basis and thus providing a proper generalization of them.

収録刊行物

• 情報処理学会研究報告. AL, アルゴリズム研究会報告

  情報処理学会研究報告. AL, アルゴリズム研究会報告 55 37-44, 1997-01-23

  一般社団法人情報処理学会

詳細情報

• CRID: 1574231876908183808
• NII論文ID: 110002812062
• NII書誌ID: AN1009593X
• ISSN: 09196072
• 本文言語コード: en
• データソース種別:
  • CiNii Articles