超图上最大独立集问题的精确算法  

Exact algorithms for maximum independent set problem on hypergraphs

作　　者：白天 肖鸣宇 Tian BAI;Mingyu XIAO(School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China)

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《中国科学:信息科学》2024年第12期2709-2726,共18页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:62372095);四川省自然科学基金(批准号:2023NSFSC0059)资助项目。

摘　　要：最大独立集问题是计算机科学中最基础且重要的NP完全问题之一.本文研究了超图上最大独立集问题(MISH)和超图上带惩罚的最大独立集问题(PC-MISH)的精确算法.给定一个超图,MISH问题旨在寻找图中最大的独立集,其中,超图中的独立集是一些两两不包含在同一超边的顶点构成的点子集.而PC-MISH问题是MISH问题的松弛化变体.在PC-MISH问题中,仍然寻找一个点集X,但是它允许违背“独立”的性质,也就是说,允许超边包含X中的多个顶点.这个集合X的价值定义为X的大小减去包含至少两个X中的顶点的超边数量.而PC-MISH问题旨在找到一个价值最大的点集.本文研究MISH和PC-MISH问题以n以及ℓ=n+m为参数的精确算法,其中n是超图中顶点的个数,m是超图中超边的条数.通过利用最大独立集问题在一般无向图上的精确算法可以直接得到MISH问题O^(∗)(1.1996^(n))时间的算法.此外,本文证明了PC-MISH问题可以在O^(∗)(1.9548^(n))时间内求解,打破了穷举搜索的2^(n)时间复杂度.进一步,本文重点给出MISH问题一个O(1.1520^(ℓ))时间的算法和PC-MISH问题一个O(1.3982^(ℓ))时间的算法,分别改进之前时间为O(1.1550^(ℓ))和1.5^(ℓ)2^(o(ℓ))的精确算法.The maximum independent set problem is one of the most fundamental and significant NP-complete problems in computer science.This paper studies exact algorithms for the maximum independent set problem on hypergraphs(MISH)and the prize-collecting maximum independent set problem on hypergraphs(PC-MISH).Given a hypergraph,MISH aims tofind a maximum independent set,where an independent set in the hypergraph is a subset of vertices such that no two vertices are contained in the same hyperedge.The PC-MISH problem is a relaxation of the MISH problem.In this problem,it is allowed tofind a non-independent set X that violates the independence constraints on some hyperedges,that is,these hyperedges contain more than one vertices.The prize of the subset X is defined as the number of vertices minus the number of hyperedges on which X violates the independence constraint.In PC-MISH,we are asked tofind a subset of vertices with the maximum prize.This paper studies the exact algorithms for both MISH and PC-MISH parameterized by two parameters n andℓ=n+m,where n is the number of vertices and m is the number of hyperedges.Using the exact algorithm for the maximum independent set problem in undirected graphs,an O^(∗)(1.1996^(n))-time for MISH can be directly obtained.In this paper,we show that PC-MISH can be solved in O^(∗)(1.9548^(n))time,breaking the 2^(n)-barrier.Furthermore,this paper proposes an O(1.1520^(ℓ))-time algorithm for MISH and an O(1.3982^(ℓ))-time algorithm for PC-MISH.These two results improve the previous time bound O(1.1550^(ℓ))and 1.5^(ℓ)2 ^(o(ℓ))for the MISH and PC-MISH problems,respectively.

关 键 词：精确算法 最大独立集问题 带惩罚最大独立集问题 超图 最小子集反馈集问题 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]