The Positive Influence Dominating Set Problem (PIDS) is a variant of the well-known Dominating Set Problem. It involves selecting a subset of vertices that positively dominate the remaining vertices in a given graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$G=(V,E)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. More formally, a vertex <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$v_i \in V$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>v</mi> <mi>i</mi> </msub> <mo>∈</mo> <mi>V</mi> </mrow> </math></EquationSource> </InlineEquation> is said to be positively dominated if at least a portion of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\rho deg_G(v_i)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ρ</mi> <mi>d</mi> <mi>e</mi> <msub> <mi>g</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mi>i</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of its neighbors belongs to the selected set, where <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$deg_G(v_i)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mi>e</mi> <msub> <mi>g</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mi>i</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the degree of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$v_i$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>v</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$0<\rho <1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo><</mo> <mi>ρ</mi> <mo><</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> is the influence factor. The objective is to identify the smallest subset of positive influence dominants. This problem is NP-hard on general graphs and remains computationally challenging even for particular classes of graphs. In this paper, we propose an efficient algorithm for solving PIDS, based on the Local Branching approach combined with the CPLEX mathematical programming solver, especially to enhance intensification and provide a good partial solution. Also, to ensure solution diversification, we develop a destructive-reconstructive greedy heuristic to explore previously unvisited subspaces. We conduct extensive experiments to evaluate our method on real-world benchmark instances of varying sizes, including large-scale graphs, and compare it with five existing state-of-the-art solving approaches. The experimental results demonstrate that the proposed approach yields high-quality solutions within reasonable computational times, highlighting its performance for efficiently solving PIDS.

Influence maximization: a local branching algorithm for solving the positive influence dominating set problem

期刊论文
发表日期：

2026年5月4日

查看全文

Yamina Bekhti,
Mohammed Lalou,
Méziane Aïder,
Hamamache Kheddouci

摘要

The Positive Influence Dominating Set Problem (PIDS) is a variant of the well-known Dominating Set Problem. It involves selecting a subset of vertices that positively dominate the remaining vertices in a given graph $G=(V,E)$ $G = (V, E)$ . More formally, a vertex $v_i \in V$ $v_{i} \in V$ is said to be positively dominated if at least a portion of $\rho deg_G(v_i)$ $ρ d e g_{G} (v_{i})$ of its neighbors belongs to the selected set, where $deg_G(v_i)$ $d e g_{G} (v_{i})$ is the degree of $v_i$ $v_{i}$ , and $0<\rho <1$ $0 < ρ < 1$ is the influence factor. The objective is to identify the smallest subset of positive influence dominants. This problem is NP-hard on general graphs and remains computationally challenging even for particular classes of graphs. In this paper, we propose an efficient algorithm for solving PIDS, based on the Local Branching approach combined with the CPLEX mathematical programming solver, especially to enhance intensification and provide a good partial solution. Also, to ensure solution diversification, we develop a destructive-reconstructive greedy heuristic to explore previously unvisited subspaces. We conduct extensive experiments to evaluate our method on real-world benchmark instances of varying sizes, including large-scale graphs, and compare it with five existing state-of-the-art solving approaches. The experimental results demonstrate that the proposed approach yields high-quality solutions within reasonable computational times, highlighting its performance for efficiently solving PIDS.