Exact algorithms for maximum independent set problem on hypergraphs
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 to find 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 to find 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 to find 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.1996n)-time for MISH can be directly obtained.In this paper,we show that PC-MISH can be solved in O*(1.9548n)time,breaking the 2n-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ℓ2o(ℓ)for the MISH and PC-MISH problems,respectively.
exact algorithmsmaximum independent set problemprize-collecting maximum independent set problemhypergraphsminimum subset feedback vertex set problem
NETL
NSTL
万方数据
