# Dual-Neighborhood Tabu Search for Computing Stable Extensions in Abstract Argumentation Frameworks  
Yuanzhi Ke  
School of Computer Science, Hubei University of Technology, Wuhan 430068, China;  
[EMAIL_ADDRESS] (Y.K. ); [EMAIL_ADDRESS] (C.H. ); [EMAIL_ADDRESS] (J.S. ); [EMAIL_ADDRESS] (C.X. ); [EMAIL_ADDRESS] (M.L.) [PERSON], [PERSON], [PERSON]. [PERSON], [PERSON]. [PERSON]  
In the field of research on formal argumentation modeling, the problem of semantic parsing in the theory of abstract argumentation frameworks [6] is particularly prominent. The International Competition on Computational Models of Argumentation (ICCMA) has been launched specifically for this purpose, in order to promote this field of research. The competition consists of several competition tracks aimed at solving a series of related problems. The research in this paper is on one of its main tracks and focuses on exploring solution strategies for computing a single stable extension of an abstract argumentation framework. Currently, algorithms for solving the stable extensions problem are mainly divided into two categories [7]: reduction-based approaches and direct approaches. Reduction-based approaches typically employ efficient existing solvers, such as SAT solvers [8], to transform abstract argumentation frameworks and stable extensions into a format that the solver can handle. In the main track of the International Competition on Computational Models of Argumentation (ICCMA), the majority of algorithms that perform outstandingly adopt reduction-based approaches, including the u-toksia [9] algorithm and the pyglaf [10] algorithm. The other category is direct approaches, which provide solutions directly for arguments on the abstract argumentation framework. These methods are typically based on labeling theory [11]. This approach was pioneered by [PERSON] [12] and was later expanded by [PERSON] [11], [PERSON] [13], and [PERSON] [14]. The most prominent variant is the 3-valued labelings proposed by [PERSON] and [PERSON] [11]. The first labeling-based algorithm framework was proposed by [PERSON] and [PERSON] [15]. The core idea of labeling-based algorithms is that, once the label of an argument is determined, it immediately affects the potential labels of its adjacent arguments. In recent years, most of the algorithms for computing stable extensions have been based on invoking SAT solvers or other types of solvers, with relatively fewer studies employing direct approaches. In research on solving abstract argumentation problems using local search approaches, [PERSON] [16] and [PERSON] [17] have explored the use of stochastic local search methods. However, the work of [PERSON] et al. focuses on solving the preferred extensions, and their approach conceptually differs from the present study. They operate on the CNF representation of the problem and apply the Swcca algorithm [18]. Therefore, their approach is essentially reduction-based rather than direct. The HAY-WOOD algorithm proposed by [PERSON] in 2018 is a direct approach based on heuristic information for local search [19], mainly expanding the search space through a stochastic selection mechanism [20]. Similarly, the approach proposed in this paper also adopts a direct approach. Due to the NP-hardness of the problem, the current algorithms that accurately determine whether a stable extension exists are all exponential in time complexity. Meta-heuristic approaches, such as tabu search, attempt to find solutions to NP-hard problems in polynomial time. Although they cannot guarantee a solution or prove its absence, meta-heuristics are more efficient in solving large-scale NP-hard problems than exact algorithms. Tabu search enhances the performance of local search by relaxing the basic rules of local search. It forbids certain previously experienced operations by establishing a tabu list based on neighborhood search.