随机图点覆盖1度顶点核化算法分析

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.     

低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法．通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1．1033^n),参数化的3度图点覆盖问题的解决时间为O(kn 1．2174^k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1．1033^n)的解．以上3结果均打破原有最佳下界。     

Ising图模型概率推理的参数化复杂性

Ising图模型概率推理的主要工作是通过变量求和来计算配分函数和边缘概率分布。传统计算复杂性理论证明Ising图模型精确概率推理是NP难的,并且Ising图模型近似概率推理是NP难的。研究了Ising图模型精确概率推理和Ising均值场近似概率推理的参数化复杂性。首先证明了不同参数的Ising图模型概率推理的参数化复杂性定理,指出基于变量个数或图模型树宽的参数化概率推理问题是固定参数可处理的。然后证明了Ising均值场的参数化复杂性定理,指出基于自由分布树宽、迭代次数和变量个数的参数化Icing均值场是固定参数可处理的;进一步,当Ising图模型参数满足Ising均值场迭代式压缩条件时,基于自由分布树宽和迭代次数的参数化Ising均值场是固定参数可处理的。     

顶点覆盖问题线性内核算法

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).     

时态图顶点介数中心度计算方法

在社会网络分析中,介数中心度用于衡量顶点对网络结构的贡献大小,是一种广泛使用的顶点重要度衡量指标.该指标主要通过计算经过顶点的最短路径数来表明顶点的重要性.目前研究的介数中心度算法主要聚焦在普通图上,针对时态图的研究工作较少.普通图介数中心度计算方法主要依据Brandes算法设计,Brandes算法有效的关键理论是最短路径的子路径依然是最短路径,即最优子结构特性.然而时态图包含时态信息,时态路径类型多样,并且时态最短路径并不满足此特性,因此普通图介数中心度计算理论与方法不再适用于时态图.鉴于此,定义了严格（时态递增）和非严格（时态非递减）2种时态路径类型,并研究了时态图介数中心度计算理论与方法.提出了一种高效的基于消息传播的2阶段迭代计算框架.第1阶段采用自顶向下的广度优先遍历方式计算时态最短路径;第2阶段采用自底向上的方式计算顶点的后继节点和孩子节点对其介数中心度的贡献值,并设计了基于消息传播机制的迭代累积计算方法.为了提高效率和可扩展性,实现了基于OpenMP(open multiprocessing)框架的多线程并行算法FTBC(fast temporal betweenness...     

随机图的点可区别全染色算法

点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数.提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功.实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3).     

多Agent动态影响图的近似计算方法

由于复杂系统具有高维性和不确定性常难以表示处理,因而知识表示和计算方法是复杂系统研究中的公开难题.当前,多Agent影响图不能建模动态环境和多Agent,马尔可夫决策过程难以表示Agents之间结构关系的问题,因而提出一种用局部概率因式表示动态环境中多Agent之间关系的新决策模型--多Agent动态影响图(MADIDs).针对MADIDs模型的联合概率分布和联合效用函数在计算上的高维问题,研究该模型的近似计算方法.给出MADIDs概率结构部分的一种分层分解的分布近似方法,并通过对该近似方法的误差和复杂性的分析,给出一个可对近似分布的精度和复杂性进行均衡的函数δ(k);给出一种BP神经网络通过局部效用的学习来近似计算MADIDs的联合效用.在模型实例上的实验结果显示了MADIDs模型近似计算方法的有效性.     

一种基于链暗示技术的Min-CVCB问题的精确算法

随着VLSI(超大规模集成电路)技术的发展,关于可重构阵列二分图的受约束最小点覆盖(Min-CVCB)问题受到了很多文献的关注.作为点覆盖问题的子问题,该问题已被证明是NP-完全问题.人们利用核心化和分支即使给出了时间复杂度为O((ku k1)|G| 1.26ku k1)的目前最好算法,然而仍不能满足实际工程的需要.通过进一步深入分析二分图的结构,对含有权值大于或等于3的块的连通子图分析其可能连接情况后充分利用"链暗示"技术和分枝搜索技术来建立起新的搜索递推关系;对于分枝后的块提出了一种动态规划算法,其可在多项式时间内完成处理.整个参数算法的运行时间为O((ku k1)|G| 1.1892ku k1),极大地改进了目前的最好结果.     

稀疏可交换图建模研究综述

可交换性假设是采用贝叶斯模型对网络数据建模的重要前提,基于Aldous-Hoover表示理论的可交换图不能生成稀疏网络.实证表明真实世界中的很多复杂网络都具有结点度幂律分布的稀疏特征,基于Kallenberg表示理论的可交换图能同时满足可交换性和稀疏性.本文以Caron-Fox模型和Graphex模型为例对稀疏可交换图建模的相关概念、理论和方法的研究发展进行了综述,首先讨论了随机图、贝叶斯非参数混合模型、可交换表示理论、Poisson点过程、离散非参数先验等理论的研究历程;然后介绍了Caron-Fox模型的表示;进而总结了进行稀疏可交换图的随机模拟所涉及的截断采样和边缘化采样方法;接下来综述了稀疏可交换图模型的后验推理技术.最后对稀疏可交换图建模的最新进展和研究前景做了介绍.     

基于图的直方图及路径相似性的图匹配方法

针对图结构在一些非刚性变换下谱特征不稳定等问题,提出一种基于几何关系直方图及路径相似性的图结构信息的描述方法,并在此基础上利用谱分析方法实现图的顶点匹配.首先通过图的直方图给出了一种图顶点的特征描述并初始化候选匹配关系,再基于最短路相似性给出一种匹配关系之间的亲和性的度量,最后采用谱方法求解2个特征点集之间对应关系,实现图的顶点的匹配.与传统的描述方法不同,该方法是利用图的直方图及路径相似性来描述图的结构信息,结构简单,信息描述充分.实验结果表明,文中方法对于一些扰动前后的图的匹配具有较高的匹配准确度.     

一种可重构阵列的最小瑕点覆盖算法

关于可重构阵列的瑕点覆盖问题受到了很多文献的关注，特别地，关于可重构阵列的最小瑕点覆盖问题等价于二分图的受约束最小点覆盖问题，并被证明是NP-完全问题。针对本问题提出的算法运行时间为O(1．19^k kn)，这里k为可替换行与列的数目，改进了原有的最好结果，其运行时间为0(1．266k kn)，较好地组合并扩展了研究参数计算的最新技术与经典匹配理论，且具有较好的实用价值。这是关于可重构阵列的最小瑕点覆盖问题算法又一较大的改进，也是目前最小点覆盖问题相关参数算法的较有意义的改进。     

On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion

For directed and undirected graphs, we study how to make a distinguished vertex the unique minimum-(in)degree vertex through deletion of a minimum number of vertices. The corresponding NP-hard optimization problems are motivated by applications concerning control in elections and social network analysis. Continuing previous work for the directed case, we show that the problem is W[2]-hard when parameterized by the graph’s feedback arc set number, whereas it becomes fixed-parameter tractable when combining the parameters “feedback vertex set number” and “number of vertices to delete”. For the so far unstudied undirected case, we show that the problem is NP-hard and W[1]-hard when parameterized by the “number of vertices to delete”. On the positive side, we show fixed-parameter tractability for several parameterizations measuring tree-likeness. In particular, we provide a dynamic programming algorithm for graphs of bounded treewidth and a vertex-linear problem kernel with respect to the parameter “feedback edge set number”. On the contrary, we show a non-existence result concerning polynomial-size problem kernels for the combined parameter “vertex cover number and number of vertices to delete”, implying corresponding non-existence results when replacing vertex cover number by treewidth or feedback vertex set number.     

On the parameterized vertex cover problem for graphs with perfect matching

A vertex cover of an n-vertex graph with perfect matching contains at least n/2 vertices.In this paper,we study the parameterized complexity of the problem vc-pm*that decides if a given graph with perfect matching has a vertex cover of size bounded by n/2+k.We first present an algorithm of running time O*(4k)for a variation of the vertex cover problem on K¨onig graphs with perfect matching.This algorithm combined with the iterative compression technique leads to an algorithm of running time O*(9k)for the problem vc-pm*.Our result improves the previous best algorithm of running time O*(15k)for the vc-pm*problem,which reduces the problem to the almost 2-sat problem and solves the latter by Razgon and O’Sullivan’s recent algorithm.     

W-Hierarchies Defined by Symmetric Gates

The classes of the W-hierarchy are the most important classes of intractable problems in parameterized complexity. These classes were originally defined via the weighted satisfiability problem for Boolean circuits. Here, besides the Boolean connectives we consider connectives such as majority, not-all-equal, and unique. For example, a gate labelled by the majority connective outputs true if more than half of its inputs are true. For any finite set C\mathcal{C} of connectives we construct the corresponding W( C\mathcal{C} )-hierarchy. We derive some general conditions which guarantee that the W-hierarchy and the W( C\mathcal{C} )-hierarchy coincide levelwise. If C\mathcal{C} only contains the majority connective then the first levels of the hierarchies coincide. We use this to show that a variant of the parameterized vertex cover problem, the majority vertex cover problem, is W[1]-complete.     

Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem

In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We consider two different measures for the problem. The first measure is a very natural multi-objective one for the use of evolutionary algorithms and takes into account the number of chosen vertices and the number of edges that remain uncovered. The second fitness function is based on a linear programming formulation and proves to give better results. We point out that both approaches lead to a kernelization for the Vertex Cover problem. Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e., the expected runtime is bounded by O(f(OPT)?n ^c ), where c is a constant and f a function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem.     

Parameterized complexity of coloring problems: Treewidth versus vertex cover

We compare the fixed parameter complexity of various variants of coloring problems (including List Coloring, Precoloring Extension, Equitable Coloring, L(p,1)-Labeling and Channel Assignment) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems.     

一种增量式约简方法求解最小顶点覆盖问题

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转化为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间;实验结果表明该算法的可行性和有效性。     

Parameterized Complexity of Vertex Cover Variants

Important variants of theVERTEX COVER problem (among others, CONNECTED VERTEX COVER, CAPACITATED VERTEX COVER, and MAXIMUM PARTIAL VERTEX COVER) have been intensively studied in terms of polynomial-time approximability. By way of contrast, their parameterized complexity has so far been completely open. We close this gap here by showing that, with the size of the desired vertex cover as the parameter, CONNECTED VERTEX COVER and CAPACITATED VERTEX COVER are both fixed-parameter tractable while MAXIMUM PARTIAL VERTEX COVER is W[1]-complete. This answers two open questions from the literature. The results extend to several closely related problems. Interestingly, although the considered variants of VERTEX COVER behave very similar in terms of constant factor approximability, they display a wide range of different characteristics when investigating their parameterized complexities.