Author name cluster

Yiyuan Wang

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.

28 papers

2 author rows

AAAI Conference 2026 Conference Paper

Improving Exact Algorithm for Pseudo Boolean Optimization with Two New Phase Selection Heuristics

Yujiao Zhao
Yizhan Xiang
Jiangnan Li
Yiyuan Wang
Minghao Yin

Pseudo-Boolean optimization (PBO) problem involves optimizing a linear objective function under linear inequality constraints defined over Boolean variables. PBO is widely used for modeling many combinational optimization problems, particularly in some real-world scenarios. In core-guided CDCL-based exact solvers, the way branching variables are assigned, known as phase selection, significantly affects the solving efficiency. This paper introduces two strategies to enhance solver performance by improving phase selection. Firstly, we design a new phase selection strategy that actively guides variables in the objective function toward assignments closer to the optimal solution. Secondly, to prevent the solver from becoming trapped in local solutions, we propose a reinforcement learning-based rephase mechanism that dynamically updates and resets variable phases. We integrate two phase selection strategies into two state-of-the-art PBO solvers and compare them against top-performing solvers from the PB competitions, using benchmarks from these competitions for assessment. The experimental results show that our solvers outperform the winning solver from the competitions.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

A Novel Local Search Algorithm for the Vertex Bisection Minimization Problem

Rui Sun
Xinyu Wang
Yiyuan Wang
Jiangnan Li
Yi Zhou

The vertex bisection minimization problem (VBMP) is a fundamental graph partitioning problem with numerous real-world applications. In this study, we propose a (k, l, S)-cluster guided local search algorithm to address this challenge. First, we propose a novel (k, l, S)-cluster enumeration procedure, which is based on two key concepts: the (k, l, S)-cluster and the local cluster core. The (k, l, S)-cluster limits both the connectivity and distinct boundaries of a given vertex set, and the local cluster core represents the most cohesive substructure within a (k, l, S)-cluster. Building up on the above (k, l, S)-cluster enumeration procedure, we present a novel (k, l, S)-cluster guided perturbation mechanism designed to escape from local optima. Next, we propose a two-manner local search procedure that employs two distinct search models to explore the neighboring search space efficiently. Experimental results demonstrate that the proposed algorithm performs best on nearly all instances.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

An Efficient Core-Guided Solver for Weighted Partial MaxSAT

Shiwei Pan
Yiyuan Wang
Shaowei Cai

The maximum satisfiability problem (MaxSAT) is a crucial combinatorial optimization problem with widespread applications across various critical domains. This paper presents CASHWMaxSAT, an efficient core-guided MaxSAT solver based on two novel ideas. The first and most important idea is the introduction of an extended stratification technique that progressively focuses on solving high-weight soft clauses. Second, we integrate disjoint unsatisfiable cores with the goal of minimizing the unsatisfiable core, allowing the solver to learn multiple high-quality clauses in a single conflict analysis step. These innovations enable our MaxSAT solver to efficiently identify key constraints and reduce redundant reasoning, significantly enhancing solving efficiency. Experimental results on benchmarks from the complete weighted track of the MaxSAT Evaluations 2022-2024 demonstrate that the proposed methods lead to substantial improvements, with CASHWMaxSAT outperforming state-of-the-art MaxSAT solvers across all benchmarks. Additionally, it enabled us to achieve the top two positions in the exact weighted category of the MaxSAT Evaluation 2024.

PDF Details DOI

ICLR Conference 2025 Conference Paper

Enhance Multi-View Classification Through Multi-Scale Alignment and Expanded Boundary

Yuena Lin
Yiyuan Wang
Gengyu Lyu
Yongjian Deng
Haichun Cai
Huibin Lin
Haobo Wang 0001
Zhen Yang 0004

Multi-view classification aims at unifying the data from multiple views to complementarily enhance the classification performance. Unfortunately, two major problems in multi-view data are damaging model performance. The first is feature heterogeneity, which makes it hard to fuse features from different views. Considering this, we introduce a multi-scale alignment module, including an instance-scale alignment module and a prototype-scale alignment module to mine the commonality from an inter-view perspective and an inter-class perspective respectively, jointly alleviating feature heterogeneity. The second is information redundancy which easily incurs ambiguous data to blur class boundaries and impair model generalization. Therefore, we propose a novel expanded boundary by extending the original class boundary with fuzzy set theory, which adaptively adjusts the boundary to fit ambiguous data. By integrating the expanded boundary into the prototype-scale alignment module, our model further tightens the produced representations and reduces boundary ambiguity. Additionally, compared with the original class boundary, the expanded boundary preserves more margins for classifying unseen data, which guarantees the model generalization. Extensive experiment results across various real-world datasets demonstrate the superiority of the proposed model against existing state-of-the-art methods.

Details

JAIR Journal 2025 Journal Article

Improving Local Search Algorithm for Pseudo Boolean Optimization

Yujiao Zhao
Yiyuan Wang
Yi Chu
Wenbo Zhou
Shaowei Cai
Minghao Yin

Pseudo-Boolean optimization (PBO) is usually used to model combinatorial optimization problems, especially for some real-world applications. Despite its significant importance in both theory and applications, the performance of current PBO solvers is still limited. This paper develops a novel local search algorithm for PBO, which has four main ideas. First, we design a new primary scoring function and a two-level selection strategy to evaluate all candidate variables. Second, we introduce a new weighting scheme to accurately guide the search process toward more promising directions. Third, we propose a novel deep optimization strategy to disturb some search processes. Fourth, an efficient solution space exploration mechanism is applied to help the algorithm jump out of local optimum. We conduct experiments on a broad range of public benchmarks, including three large-scale practical application benchmarks, two benchmarks from PB competitions, an integer linear programming optimization benchmark, a crafted combinatorial benchmark, and a combinatorial optimization knapsack benchmark to compare our proposed algorithm against twelve state-of-the-art competitors, including seven recently-proposed pure stochastic local search PBO solvers, a non-traditional stochastic local search combined with complete oracle, two complete PB solvers, and two mixed integer programming (MIP) solvers. Our proposed algorithm has been shown to perform best on these three real-world benchmarks. On the other five benchmarks, our algorithm shows competitive performance compared to state-of-the-art competitors, and it significantly outperforms all other local search algorithms, indicating that our algorithm greatly advances the state of the art in local search for solving PBO.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

InfVC: An Inference-Enhanced Local Search Algorithm for the Minimum Vertex Cover Problem in Massive Graphs

Rui Sun
Peiyan Liu
Yiyuan Wang
Zhaohui Liu
Liping Du
Jian Gao

The minimum vertex cover (MVC) problem is a classic NP-hard combinatorial optimization problem with extensive real-world applications. In this paper, we propose an efficient local search algorithm, InfVC, to solve the MVC in massive graphs, which comprises three ideas. First, we introduce an inference-driven optimization strategy that explores better feasible solutions through inference rules. Second, we develop a structural-determined perturbation strategy that is motivated by the structure features of high-quality solutions, prioritizing high-degree vertices into the candidate solution to guide the search process to some potential high-quality search area. Third, we design a self-adaptive local search framework that dynamically balances exploration and exploitation through a perturbation management mechanism. Extensive experiments demonstrate that InfVC outperforms all the state-of-the-art algorithms on almost massive instances.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem

Rui Sun
Zhaohui Liu
Yiyuan Wang
Han Xiao
Jiangnan Li
Jiejiang Chen

The minimum dominating set (MDS) problem is a crucial NP-hard combinatorial optimization problem with wide applications in real-world scenarios. In this paper, we propose an efficient local search algorithm namely NuMDS to solve the MDS, which comprises three key ideas. First, we introduce a dominate propagation-based reduction method that fixes a portion of vertices in a given graph. Second, we develop a novel two-phase initialization method based on the decomposition method. Third, we propose a multi-stage local search procedure, which adopts three different search manners according to the current stage of the search. We conduct extensive experiments to demonstrate the outstanding effectiveness of NuMDS, and the results clearly indicate that NuMDS outperforms previous state-of-the-art algorithms on almost all instances.

PDF Details DOI

EAAI Journal 2024 Journal Article

A local search algorithm with movement gap and adaptive configuration checking for the maximum weighted s-plex problem

Ruizhi Li
Ruiqi Xu
Fangzhou Wang
Shuli Hu
Yiyuan Wang
Minghao Yin
Hui Li

The maximum weighted s-plex problem (MWSP) is an important generalization of the maximum s-plex problem and has a wide range of applications in many fields such as social network analysis. In this paper, we propose an efficient local search algorithm based on movement gap and adaptive configuration checking. Firstly, we use f l i p to construct the initial solution and select more suitable vertices to jump out of the local optimum. Secondly, we propose a novel variant of configuration checking with stronger automatic adjustment capability, called adaptive configuration checking (ACC), which can effectively avoid the cycling problem in local search. Besides, we use three operators Add, Swap, and Drop to improve the solution. Our algorithm determines the operator by the increment and judges which vertices are more likely to appear in the solution based on the movement gap (MG) of each vertex. In the perturbation phase, we use the Jump operator to escape the local optimum and adopt the best from multiple selections based on the dynamic parameter (DPBMS) heuristic to improve the search efficiency. By comparing the current state-of-the-art algorithms, we demonstrate that our method performs well. In addition, we validate the effectiveness of the ACC and MG strategies throughout the algorithm and the role of the DPBMS heuristic in the perturbation procedure.

Details DOI

IJCAI Conference 2024 Conference Paper

Nukplex: An Efficient Local Search Algorithm for Maximum K-Plex Problem

Rui Sun
Yiyuan Wang
Shimao Wang
Hui Li
Ximing Li
Minghao Yin

The maximum k-plex problem (MKPP) is an significant relaxation version of the maximum clique problem with extensive applications. Recently, lots of researchers have proposed many heuristic algorithms based on various methods to solve the MKPP. In this work, to further improve the performance of solving the MKPP, we propose an efficient local search algorithm based on three main ideas. First, we propose a relaxed bounded configuration checking strategy that considers two kinds of historical searching information to relax the restricted strength of configuration checking and the forbidden condition of candidate vertices for the operation Add, respectively. Second, we present a novel solution information-based vertex selection strategy based on two kinds of solution information to select high-quality candidate vertices. Third, we define the solution core and then introduce a core-based perturbation strategy to help the algorithm jump out of local optima. The experimental results show that the proposed algorithm significantly outperforms the state-of-the-art MKPP algorithms in almost all the instances.

PDF Details DOI

AIJ Journal 2024 Journal Article

PathLAD+: Towards effective exact methods for subgraph isomorphism problem

Yiyuan Wang
Chenghou Jin
Shaowei Cai

The subgraph isomorphism problem (SIP) is a challenging problem with wide practical applications. In the last decade, despite being a theoretical hard problem, researchers designed various algorithms for solving SIP. In this work, we propose five main strategies and develop an improved exact algorithm for SIP. First, we design a probing search procedure to try whether the search procedure can successfully obtain a solution at first sight. Second, we design a novel matching ordering strategy as a value-ordering heuristic, which uses some useful information obtained from the probing search procedure to preferentially select some promising target vertices. Third, we discuss the characteristics of different propagation methods in the context of SIP and present an adaptive propagation method to make a good balance between these methods. Moreover, to further improve the performance of solving large graphs, we propose an enhanced implementation of the edge constraint method and a domain limitation strategy, which aims to accelerate the search process. Experimental results on a broad range of classic and graph-database benchmarks show that our proposed algorithm performs better than several state-of-the-art algorithms for the SIP.

Details DOI

AIJ Journal 2023 Journal Article

Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism

Jiejiang Chen
Shaowei Cai
Yiyuan Wang
Wenhao Xu
Jia Ji
Minghao Yin

The minimum weight dominating set (MWDS) problem is an important generalization of the minimum dominating set problem with various applications. In this work, we develop an efficient local search scheme that can dynamically adjust the number of added and removed vertices according to the information of the candidate solution. Based on this scheme, we further develop three novel ideas to improve performance, resulting in our so-called DeepOpt-MWDS algorithm. First, we use a new construction method with five reduction rules to significantly reduce massive graphs and construct an initial solution efficiently. Second, an improved configuration checking strategy called CC2V3+ is designed to reduce the cycling phenomenon in local search. Third, a general perturbation framework called deep optimization mechanism (DeepOpt) is proposed to help the algorithm avoid local optima and to converge to a new solution quickly. Extensive experiments based on eight popular benchmarks of different scales are carried out to evaluate the proposed algorithm. Compared to seven state-of-the-art heuristic algorithms, DeepOpt-MWDS performs better on random and classic benchmarks and obtains the best solutions on almost all massive graphs. We investigate three main algorithmic ingredients to understand their impacts on the performance of the proposed algorithm. Moreover, we adapt the proposed general framework DeepOpt to another NP-hard problem to verify its generality and achieve good performance.

Details DOI

AAAI Conference 2023 Conference Paper

Learning with Partial Labels from Semi-supervised Perspective

Ximing Li
Yuanzhi Jiang
Changchun Li
Yiyuan Wang
Jihong Ouyang

Partial Label (PL) learning refers to the task of learning from the partially labeled data, where each training instance is ambiguously equipped with a set of candidate labels but only one is valid. Advances in the recent deep PL learning literature have shown that the deep learning paradigms, e.g., self-training, contrastive learning, or class activate values, can achieve promising performance. Inspired by the impressive success of deep Semi-Supervised (SS) learning, we transform the PL learning problem into the SS learning problem, and propose a novel PL learning method, namely Partial Label learning with Semi-supervised Perspective (PLSP). Specifically, we first form the pseudo-labeled dataset by selecting a small number of reliable pseudo-labeled instances with high-confidence prediction scores and treating the remaining instances as pseudo-unlabeled ones. Then we design a SS learning objective, consisting of a supervised loss for pseudo-labeled instances and a semantic consistency regularization for pseudo-unlabeled instances. We further introduce a complementary regularization for those non-candidate labels to constrain the model predictions on them to be as small as possible. Empirical results demonstrate that PLSP significantly outperforms the existing PL baseline methods, especially on high ambiguity levels. Code available: https://github.com/changchunli/PLSP.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

PathLAD+: An Improved Exact Algorithm for Subgraph Isomorphism Problem

Yiyuan Wang
Chenghou Jin
Shaowei Cai
Qingwei Lin

The subgraph isomorphism problem (SIP) is a challenging problem with wide practical applications. In the last decade, despite being a theoretical hard problem, researchers design various algorithms for solving SIP. In this work, we propose three main heuristics and develop an improved exact algorithm for SIP. First, we design a probing search procedure to try whether the search procedure can successfully obtain a solution at first sight. Second, we design a novel matching ordering as a value-ordering heuristic, which uses some useful information obtained from the probing search procedure to preferentially select some promising target vertices. Third, we discuss the characteristics of different propagation methods in the context of SIP and present an adaptive propagation method to make a good balance between these methods. Experimental results on a broad range of real-world benchmarks show that our proposed algorithm performs better than state-of-the-art algorithms for the SIP.

PDF Details DOI

AAAI Conference 2022 Conference Paper

A Fast Local Search Algorithm for the Latin Square Completion Problem

Shiwei Pan
Yiyuan Wang
Minghao Yin

The Latin square completion (LSC) problem is an important NP-complete problem with numerous applications. Given its theoretical and practical importance, several algorithms are designed for solving the LSC problem. In this work, to further improve the performance, a fast local search algorithm is developed based on three main ideas. Firstly, a reduction reasoning technique is used to reduce the scale of search space. Secondly, we propose a novel conflict value selection heuristic, which considers the history conflicting information of vertices as a selection criterion when more than one vertex have equal values on the primary scoring function. Thirdly, during the search phase, we record previous history search information and then make use of these information to restart the candidate solution. Experimental results show that our proposed algorithm significantly outperforms the stateof-the-art heuristic algorithms on almost all instances in terms of success rate and run time.

PDF Details

AAAI Conference 2022 Conference Paper

NukCP: An Improved Local Search Algorithm for Maximum k-Club Problem

Jiejiang Chen
Yiyuan Wang
Shaowei Cai
Minghao Yin
Yupeng Zhou
Jieyu Wu

The maximum k-club problem (MkCP) is an important clique relaxation problem with wide applications. Previous MkCP algorithms only work on small-scale instances and are not applicable for large-scale instances. For solving instances with different scales, this paper develops an efficient local search algorithm named NukCP for the MkCP which mainly includes two novel ideas. First, we propose a dynamic reduction strategy, which makes a good balance between the time efficiency and the precision effectiveness of the upper bound calculation. Second, a stratified threshold configuration checking strategy is designed by giving different priorities for the neighborhood in the different levels. Experiments on a broad range of different scale instances show that NukCP significantly outperforms the state-of-the-art MkCP algorithms on most instances in terms of solution quality.

PDF Details

JAIR Journal 2021 Journal Article

A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs

Shaowei Cai
Jinkun Lin
Yiyuan Wang
Darren Strash

This paper explores techniques to quickly solve the maximum weight clique problem (MWCP) in very large scale sparse graphs. Due to their size, and the hardness of MWCP, it is infeasible to solve many of these graphs with exact algorithms. Although recent heuristic algorithms make progress in solving MWCP in large graphs, they still need considerable time to get a high-quality solution. In this work, we focus on solving MWCP for large sparse graphs within a short time limit. We propose a new method for MWCP which interleaves clique finding with data reduction rules. We propose novel ideas to make this process efficient, and develop an algorithm called FastWClq. Experiments on a broad range of large sparse graphs show that FastWClq finds better solutions than state-of-the-art algorithms while the running time of FastWClq is much shorter than the competitors for most instances. Further, FastWClq proves the optimality of its solutions for roughly half of the graphs, all with at least 105 vertices, with an average time of 21 seconds.

PDF Details DOI

JAIR Journal 2021 Journal Article

Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set

Xindi Zhang
Bohan Li
Shaowei Cai
Yiyuan Wang

The minimum connected dominating set (MCDS) problem is an important extension of the minimum dominating set problem, with wide applications, especially in wireless networks. Most previous works focused on solving MCDS problem in graphs with relatively small size, mainly due to the complexity of maintaining connectivity. This paper explores techniques for solving MCDS problem in massive real-world graphs with wide practical importance. Firstly, we propose a local greedy construction method with reasoning rule called 1hopReason. Secondly and most importantly, a hybrid dynamic connectivity maintenance method (HDC+) is designed to switch alternately between a novel fast connectivity maintenance method based on spanning tree and its previous counterpart. Thirdly, we adopt a two-level vertex selection heuristic with a newly proposed scoring function called chronosafety to make the algorithm more considerate when selecting vertices. We design a new local search algorithm called FastCDS based on the three ideas. Experiments show that FastCDS significantly outperforms five state-of-the-art MCDS algorithms on both massive graphs and classic benchmarks.

PDF Details DOI

AAAI Conference 2021 Short Paper

Generating Long Financial Report using Conditional Variational Autoencoders with Knowledge Distillation

Yunpeng Ren
Ziao Wang
Yiyuan Wang
Xiaofeng Zhang

Automatically generating financial report from a piece of news is quite a challenging task. Apparently, the difficulty of this task lies in the lack of sufficient background knowledge to effectively generate long financial report. To address this issue, this paper proposes the conditional variational autoencoders (CVAE) based approach which distills external knowledge from a corpus of news-report data, and experimental results show that it can achieve the SOTA performance.

PDF Details

AAAI Conference 2021 Conference Paper

NuQClq: An Effective Local Search Algorithm for Maximum Quasi-Clique Problem

Jiejiang Chen
Shaowei Cai
Shiwei Pan
Yiyuan Wang
Qingwei Lin
Mengyu Zhao
Minghao Yin

The maximum quasi-clique problem (MQCP) is an important extension of maximum clique problem with wide applications. Recent heuristic MQCP algorithms can hardly solve large and hard graphs effectively. This paper develops an efficient local search algorithm named NuQClq for the MQCP, which has two main ideas. First, we propose a novel vertex selection strategy, which utilizes cumulative saturation information to be a selection criterion when the candidate vertices have equal values on the primary scoring function. Second, a variant of configuration checking named BoundedCC is designed by setting an upper bound for the threshold of forbidding strength. When the threshold value of vertex exceeds the upper bound, we reset its threshold value to increase the diversity of search process. Experiments on a broad range of classic benchmarks and sparse instances show that NuQ- Clq significantly outperforms the state-of-the-art MQCP algorithms for most instances.

PDF Details

IJCAI Conference 2020 Conference Paper

NuCDS: An Efficient Local Search Algorithm for Minimum Connected Dominating Set

Bohan Li
Xindi Zhang
Shaowei Cai
Jinkun Lin
Yiyuan Wang
Christian Blum

The minimum connected dominating set (MCDS) problem is an important extension of the minimum dominating set problem, with wide applications, especially in wireless networks. Despite its practical importance, there are few works on solving MCDS for massive graphs, mainly due to the complexity of maintaining connectivity. In this paper, we propose two novel ideas, and develop a new local search algorithm for MCDS called NuCDS. First, a hybrid dynamic connectivity maintenance method is designed to switch alternately between a novel fast connectivity maintenance method based on spanning tree and its previous counterpart. Second, we define a new vertex property called \emph{safety} to make the algorithm more considerate when selecting vertices. Experiments show that NuCDS significantly outperforms the state-of-the-art MCDS algorithms on both massive graphs and classic benchmarks.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Reduction and Local Search for Weighted Graph Coloring Problem

Yiyuan Wang
Shaowei Cai
Shiwei Pan
Ximing Li
Monghao Yin

The weighted graph coloring problem (WGCP) is an important extension of the graph coloring problem (GCP) with wide applications. Compared to GCP, where numerous methods have been developed and even massive graphs with millions of vertices can be solved well, fewer works have been done for WGCP, and no solution is available for solving WGCP for massive graphs. This paper explores techniques for solving WGCP, including a lower bound and a reduction rule based on clique sampling, and a local search algorithm based on two selection rules and a new variant of conﬁguration checking. This results in our algorithm RedLS (Reduction plus Local Search). Experiments are conducted to compare RedLS with the state-of-the-art algorithms on massive graphs as well as conventional benchmarks studied in previous works. RedLS exhibits very good performance and robustness. It signiﬁcantly outperforms previous algorithms on all benchmarks.

PDF Details

AIJ Journal 2020 Journal Article

SCCWalk: An efficient local search algorithm and its improvements for maximum weight clique problem

Yiyuan Wang
Shaowei Cai
Jiejiang Chen
Minghao Yin

The maximum weight clique problem (MWCP) is an important generalization of the maximum clique problem with wide applications. In this study, we develop two efficient local search algorithms for MWCP, namely SCCWalk and SCCWalk4L, where SCCWalk4L is improved from SCCWalk for large graphs. There are two main ideas in SCCWalk, including strong configuration checking (SCC) and walk perturbation. SCC is a new variant of a powerful strategy called configuration checking for local search. The walk perturbation procedure is used to lead the algorithm to leave the current area and come into a new area of feasible solution space. Moreover, to improve the performance on massive graphs, we apply a low-complexity heuristic called best from multiple selection to select the swapping vertex pair quickly and effectively, resulting in the SCCWalk4L algorithm. In addition, SCCWalk4L uses two recent reduction rules to decrease the scale of massive graphs. We carry out experiments to evaluate our algorithms on several popular benchmarks, which are divided into two groups, including classical benchmarks of small graphs namely DIMACS, BHOSLIB, winner determination problem, and graphs derived from clustering aggregation, as well as massive graphs, including a suite of massive real-world graphs and large-scale FRB graphs. Experiments show that, compared to state-of-the-art heuristic algorithms and exact algorithm, the proposed algorithms perform better on classical benchmarks, and obtain the best solutions for most massive graphs.

Details DOI

IJCAI Conference 2020 Conference Paper

Two-goal Local Search and Inference Rules for Minimum Dominating Set

Shaowei Cai
Wenying Hou
Yiyuan Wang
Chuan Luo
Qingwei Lin

Minimum dominating set (MinDS) is a canonical NP-hard combinatorial optimization problem with applications. For large and hard instances one must resort to heuristic approaches to obtain good solutions within reasonable time. This paper develops an efficient local search algorithm for MinDS, which has two main ideas. The first one is a novel local search framework, while the second is a construction procedure with inference rules. Our algorithm named FastDS is evaluated on 4 standard benchmarks and 3 massive graphs benchmarks. FastDS obtains the best performance for almost all benchmarks, and obtains better solutions than state-of-the-art algorithms on massive graphs.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

A Fast Local Search Algorithm for Minimum Weight Dominating Set Problem on Massive Graphs

Yiyuan Wang
Shaowei Cai
Jiejiang Chen
Minghao Yin

The minimum weight dominating set (MWDS) problem is NP-hard and also important in many applications. Recent heuristic MWDS algorithms can hardly solve massive real world graphs effectively. In this paper, we design a fast local search algorithm called FastMWDS for the MWDS problem, which aims to obtain a good solution on massive graphs within a short time. In this novel local search framework, we propose two ideas to make it effective. Firstly, we design a new fast construction procedure with four reduction rules to cut down the size of massive graphs. Secondly, we propose the three-valued two-level configuration checking strategy to improve local search, which is interestingly a variant of configuration checking (CC) with two levels and multiple values. Experiment results on a broad range of massive real world graphs show that FastMWDS finds much better solutions than state of the art MWDS algorithms.

PDF Details

IJCAI Conference 2018 Conference Paper

An Exact Algorithm for Maximum k-Plexes in Massive Graphs

Jian Gao
Jiejiang Chen
Minghao Yin
Rong Chen
Yiyuan Wang

The maximum k-plex, a generalization of maximum clique, is used to cope with a great number of real-world problems. The aim of this paper is to propose a novel exact k-plex algorithm that can deal with large-scaled graphs with millions of vertices and edges. Specifically, we first propose several new graph reduction methods through a careful analyzing of structures of induced subgraphs. Afterwards, we present a preprocessing method to simplify initial graphs. Additionally, we present a branch-and-bound algorithm integrating the reduction methods as well as a new dynamic vertex selection mechanism. We perform intensive experiments to evaluate our algorithm, and show that the proposed strategies are effective and our algorithm outperforms state-of-the-art algorithms, especially for real-world massive graphs.

PDF Details

JAIR Journal 2017 Journal Article

Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function

Yiyuan Wang
Shaowei Cai
Minghao Yin

The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS problem, which is based on two new ideas. The first idea is a heuristic called two-level configuration checking (CC2), which is a new variant of a recent powerful configuration checking strategy (CC) for effectively avoiding the recent search paths. The second idea is a novel scoring function based on the frequency of being uncovered of vertices. Our algorithm is called CC2FS, according to the names of the two ideas. The experimental results show that, CC2FS performs much better than some state-of-the-art algorithms in terms of solution quality on a broad range of MWDS benchmarks.

PDF Details DOI

IJCAI Conference 2017 Conference Paper

Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function (Extended Abstract)

Yiyuan Wang
Shaowei Cai
Minghao Yin

PDF Details

AAAI Conference 2016 Conference Paper

Two Efficient Local Search Algorithms for Maximum Weight Clique Problem

Yiyuan Wang
Shaowei Cai
Minghao Yin

The Maximum Weight Clique problem (MWCP) is an important generalization of the Maximum Clique problem with wide applications. This paper introduces two heuristics and develops two local search algorithms for MWCP. Firstly, we propose a heuristic called strong conﬁguration checking (SCC), which is a new variant of a recent powerful strategy called conﬁguration checking (CC) for reducing cycling in local search. Based on the SCC strategy, we develop a local search algorithm named LSCC. Moreover, to improve the performance on massive graphs, we apply a low-complexity heuristic called Best from Multiple Selection (BMS) to select the swapping vertex pair quickly and effectively. The BMS heuristic is used to improve LSCC, resulting in the LSCC+BMS algorithm. Experiments show that the proposed algorithms outperform the state-of-the-art local search algorithm MN/TS and its improved version MN/TS+BMS on the standard benchmarks namely DIMACS and BHOSLIB, as well as a wide range of real world massive graphs.

PDF Details