Author name cluster

Enqiang Zhu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

AAAI Conference 2026 Conference Paper

Exact Optimization for Minimum Dominating Sets

Enqiang Zhu
Qiqi Bao
Yu Zhang
Chanjuan Liu
Pu Wu

The Minimum Dominating Set (MDS) problem is a well-established combinatorial optimization problem with numerous real-world applications. Its NP-hard nature makes it increasingly difficult to obtain exact solutions as the graph size grows. This paper introduces ParDS, an exact algorithm developed to address the MDS problem within the branch-and-bound framework. ParDS features two key innovations: an advanced linear programming technique that yields tighter lower bounds and a set of novel reduction rules that dynamically simplify instances throughout the solving process. Compared to the leading exact algorithms presented at IJCAI 2023 and 2024, ParDS demonstrates theoretically superior lower-bound quality. Experimental results on standard benchmark datasets highlight several significant advantages of ParDS: it achieves fastest solving times in 70% of graph categories, especially on large, sparse graphs, delivers a speed-up of up to 3,411 times on the fastest individual instance, and successfully solves 16 out of 43 instances that other algorithms were unable to resolve within the 5-hour time limit. These findings establish ParDS as a state-of-the-art solution for exactly solving the MDS problem

PDF Details DOI

EAAI Journal 2025 Journal Article

Critical nodes detection for complex networks via knowledge-guided evolutionary framework

Chanjuan Liu
Shike Ge
Zhihan Chen
Wenbin Pei
Enqiang Zhu
Hisao Ishibuchi

The Critical Node Problem (CNP) focuses on identifying critical nodes within complex networks. These nodes play a crucial role in maintaining connectivity, and their removal impacts network performance. Among CNP variants, CNP-1a — which minimizes pairwise connectivity after removing a limited number of nodes — has attracted significant research attention due to its NP-hard nature and applications in diverse fields like epidemic control and infrastructure resilience. While state-of-the-art methods leverage memetic algorithms and variable populations, they fundamentally rely on random initialization that often converges to local optima. This limitation arises because traditional methods fail to capture higher-order topological dependencies. To address this gap, we propose K2GA, a knowledge-guided genetic algorithm initialized by a graph attention network (GAT). The GAT embeds networks into low-dimensional spaces, assigning topology-aware attention weights to nodes that guide population initialization. K2GA then employs a hybrid genetic algorithm with a local search process to identify an optimal set of critical nodes. The local search process utilizes a cut node-based greedy strategy. Experiments on 26 real-world networks demonstrate that K2GA outperforms state-of-the-art methods in terms of the best, median, and average objective values, establishing new upper bounds for minimization in eight cases. This work pioneers a GAT-guided evolutionary search framework, offering a novel paradigm for solving CNP.

Details DOI

TCS Journal 2016 Journal Article

A logical characterization of extensive games with short sight

Chanjuan Liu
Fenrong Liu
Kaile Su
Enqiang Zhu

The notion of short sight, introduced by Grossi and Turrini, weakens the unrealistic assumption in traditional extensive games that every player is able to perceive the entire game structure. In this paper, we propose a more general model for extensive games with short sight. For reasoning about extensive games with short sight, we propose a new logic language and then present an axiomatization for this logic. We prove the soundness and completeness of the axiomatization. In addition, we show that the logic can formally characterize the solution concepts and Pearce's lemma in games with short sight.

Details DOI