Maximum weight t-sparse set problem on vector-weighted graphs

School of Mathematics, Southeast University, Nanjing 210096, P.R. China.

^* Corresponding author: wslin@seu.edu.cn

Received: 27 September 2022
Accepted: 9 September 2023

Abstract

Let t be a nonnegative integer and G = (V(G),E(G)) be a graph. For v ∈ V(G), let N_G(v) = {u ∈ V(G) \ {v} : uv ∈ E(G)}. And for S ⊆ V(G), we define d_S(G; v) = |N_G(v) ∩ S| for v ∈ S and d_S(G; v) = −1 for v ∈ V(G) \ S. A subset S ⊆ V(G) is called a t-sparse set of G if the maximum degree of the induced subgraph G[S] does not exceed t. In particular, a 0-sparse set is precisely an independent set. A vector-weighted graph is a graph G with a vector weight function , where for each v ∈ V(G). The weight of a t-sparse set S in is defined as . And a t-sparse set S is a maximum weight t-sparse set of if there is no t-sparse set of larger weight in . In this paper, we propose the maximum weight t-sparse set problem on vector-weighted graphs, which is to find a maximum weight t-sparse set of . We design a dynamic programming algorithm to find a maximum weight t-sparse set of an outerplane graph which takes O((t + 2)⁴n) time, where n = |V(G)|. Moreover, we give a polynomial-time algorithm for this problem on graphs with bounded treewidth.