Exact algorithms for maximum independent set problem on hypergraphs
Tian Bai, Mingyu Xiao · Scientia Sinica Informationis · 2024
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 ell = 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 mathcalO^*1.1996^n-time for MISH can be directly obtained.In this paper, we show that PC-MISH can be solved in mathcalO^*1.9548^n time, breaking the 2^n-barrier.Furthermore, this paper proposes an mathcalO1.1520^ell-time algorithm for MISH and an mathcalO1.3982^ell-time algorithm for PC-MISH.These two results improve the previous time bound mathcalO1.1550^ell and 1.5^ell2^o(ell)for the MISH and PC-MISH problems, respectively.