Related papers: Structure-Aware Encodings of Argumentation Properties for Clique-width

Structure-Aware Encodings of Argumentation Properties for Clique-width

URL: http://arxiv.org/abs/2511.10767v1
Date: Thu, 13 Nov 2025 19:36:31 GMT
Title: Structure-Aware Encodings of Argumentation Properties for Clique-width
Authors: Yasir Mahmood, Markus Hecher, Johanna Groven, Johannes K. Fichte,
Abstract summary: We study compact encodings into (Q)SAT for solving and to understand encoding limitations.<n>Although algorithms are available for clique-width, little is known about encodings.<n>Our reductions linearly preserve the clique-width, resulting in directed decomposition-guided (DDG) reductions.
Score: 19.447613152899752
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Structural measures of graphs, such as treewidth, are central tools in computational complexity resulting in efficient algorithms when exploiting the parameter. It is even known that modern SAT solvers work efficiently on instances of small treewidth. Since these solvers are widely applied, research interests in compact encodings into (Q)SAT for solving and to understand encoding limitations. Even more general is the graph parameter clique-width, which unlike treewidth can be small for dense graphs. Although algorithms are available for clique-width, little is known about encodings. We initiate the quest to understand encoding capabilities with clique-width by considering abstract argumentation, which is a robust framework for reasoning with conflicting arguments. It is based on directed graphs and asks for computationally challenging properties, making it a natural candidate to study computational properties. We design novel reductions from argumentation problems to (Q)SAT. Our reductions linearly preserve the clique-width, resulting in directed decomposition-guided (DDG) reductions. We establish novel results for all argumentation semantics, including counting. Notably, the overhead caused by our DDG reductions cannot be significantly improved under reasonable assumptions.

Related papers

Fast correlated decoding of transversal logical algorithms [67.01652927671279]
Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
arXiv Detail & Related papers (2025-05-19T18:00:00Z)
Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth [83.15263499262824]
We prove that gradient descent converges to a solution that completely disregards the sparse structure of the input. We show how to improve upon Gaussian performance for the compression of sparse data by adding a denoising function to a shallow architecture. We validate our findings on image datasets, such as CIFAR-10 and MNIST.
arXiv Detail & Related papers (2024-02-07T16:32:29Z)
Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? [21.10339925217772]
We deal with the classification of structural parameters for disjunctive ASP on the program's rule structure. We provide double-exponential lower bounds for the most prominent parameters in that range. Our results provide an in-depth hardness study, relying on a novel reduction from normal to disjunctive programs.
arXiv Detail & Related papers (2024-02-05T21:51:36Z)
A Simple and Scalable Representation for Graph Generation [13.111214838770296]
We introduce a new, simple, and scalable graph representation named gap encoded edge list (GEEL) that has a small representation size that aligns with the number of edges. GEEL significantly reduces the vocabulary size by incorporating the gap encoding and bandwidth restriction schemes. We conduct a comprehensive evaluation across ten non-attributed and two molecular graph generation tasks, demonstrating the effectiveness of GEEL.
arXiv Detail & Related papers (2023-12-04T03:43:26Z)
NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
arXiv Detail & Related papers (2023-06-14T09:21:15Z)
Solving Projected Model Counting by Utilizing Treewidth and its Limits [23.81311815698799]
We introduce a novel algorithm to solve projected model counting (PMC) Inspired by the observation that the so-called "treewidth" is one of the most prominent structural parameters, our algorithm utilizes small treewidth of the primal graph of the input instance.
arXiv Detail & Related papers (2023-05-30T17:02:07Z)
Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All? [9.480212602202517]
We show a new result establishing that, when considering treewidth, already the fragment of normal ASP is slightly harder than SAT. We present an empirical study of our novel reduction from normal ASP to SAT, where we compare treewidth upper bounds that are obtained via known decompositions.
arXiv Detail & Related papers (2022-10-07T13:40:07Z)
Advanced Tools and Methods for Treewidth-Based Problem Solving -- Extended Abstract [9.480212602202517]
This work focuses on logic-based problems and treewidth-based methods and tools for solving them. We present a new type of problem reduction, which is referred to by decomposition-guided (DG) We implement an algorithm for solving extensions of Sat efficiently, by directly using treewidth.
arXiv Detail & Related papers (2022-08-24T07:43:58Z)
Neural network relief: a pruning algorithm based on neural activity [47.57448823030151]
We propose a simple importance-score metric that deactivates unimportant connections. We achieve comparable performance for LeNet architectures on MNIST. The algorithm is not designed to minimize FLOPs when considering current hardware and software implementations.
arXiv Detail & Related papers (2021-09-22T15:33:49Z)
An Information Theory-inspired Strategy for Automatic Network Pruning [97.03772272417599]
Deep convolution neural networks are well known to be compressed on devices with resource constraints.<n>Most existing network pruning methods require laborious human efforts and prohibitive computation resources.<n>We propose an information theory-inspired strategy for automatic model compression.
arXiv Detail & Related papers (2021-08-19T07:03:22Z)
Partition and Code: learning how to compress graphs [50.29024357495154]
"Partition and Code" framework entails three steps: first, a partitioning algorithm decomposes the graph into elementary structures, then these are mapped to the elements of a small dictionary on which we learn a probability distribution, and finally, an entropy encoder translates the representation into bits. Our algorithms are quantitatively evaluated on diverse real-world networks obtaining significant performance improvements with respect to different families of non-parametric and parametric graph compressor.
arXiv Detail & Related papers (2021-07-05T11:41:16Z)
Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
We study tradeoffs of computational cost and expressive power of Graph Neural Networks (GNNs) We show that a new model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. In several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNNs.
arXiv Detail & Related papers (2020-12-06T03:42:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.