最小填充问题的可分解性

起源于稀疏矩阵计算和其它应用领域的图G的最小填充问题是在图G中寻求一个内含边数最小的边集F使得G F是弦图.这里最小值|F|称为图G的填充数,表示为f(G).作为NP-困难问题,该问题的降维性质已被研究,其中包括它的可分解性.基本的可分解定理是:如果图G的一个点割集S是一个团,则G经由S是可分解的.作为推广,如果S是一个"近似"团(即只有极少数边丢失的团),则G经由S是可分解的.本文首先给出基本分解定理的另外一个推广:如果S是G的一个极小点割集且G-S含有至少|S|个分支,则G经由S是可分解的;其次,给出了这个新推广定理的一些应用.

The Decomposability of Minimum Fill-in Problems for Graphs

The fill-in minimization problem comes from the elimination process of sparse matrix computation.In a graph-theoretic version for a graph G,it is to find a set F of added edges such that the graph G F is chordal and |F| is minimized.Here the minimum value |F| is called the finll-in number of G,denoted as f(G).This problem is known to be NP-hard.Some techniques of dimension reduction,including the decomposability of the problem,were studied in the literatures.The basic decomposition result is that if a vertex cut S of G is a clique,then G is decomposable by S.A direction of generalization is that when the cut is 'nearly' a clique (a clique with a few edges missing),G is decomposable by S.This paper presents another direction of generalization that if S is a minimal vertex cut of G and G-S has at least |S| components,then G is decomposable by S.Some applications of this theorem are also discussed.