Complexity in infinite argumentation with structural constraints

Argumentation frameworks (AFs) provide a formal setting to analyse many forms of reasoning with conflicting information. Even for finite AFs, practical use is complicated by the computational intractability of many reasoning problems. As such, a number of researchers have explored special classes of AFs, such as those defined by bipartite, acyclic or symmetric finite directed graphs, wherein many reasoning problems become tractable. In many applications, however, infinite AFs are required to adequately capture the structure of reasoning. Recent work has initiated a systematic study of the complexity of reasoning in infinite AFs using tools from computability theory, revealing that many problems in this setting are not even finite-time approximable. This paper investigates how structural constraints—specifically, bipartiteness, acyclicity and symmetry—affect the complexity of reasoning in infinite AFs. We show that in some cases, these constraints suffice to restore finite-time approximability, while in others they do not. Our results reveal the subtle role of structural properties in shaping computational behaviour, and they provide foundational insights for identifying conditions under which reasoning in infinite AFs becomes computationally feasible.