Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions?

• URL: http://arxiv.org/abs/2402.03539v1
• Date: Mon, 5 Feb 2024 21:51:36 GMT
• Title: Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions?
• Authors: Markus Hecher, Rafael Kiesel
• Abstract summary: 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.
• Score: 21.10339925217772
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Answer Set Programming (ASP) is a generic problem modeling and solving framework with a strong focus on knowledge representation and a rapid growth of industrial applications. So far, the study of complexity resulted in characterizing hardness and determining their sources, fine-grained insights in the form of dichotomy-style results, as well as detailed parameterized complexity landscapes. Unfortunately, for the well-known parameter treewidth disjunctive programs require double-exponential runtime under reasonable complexity assumptions. This quickly becomes out of reach. We deal with the classification of structural parameters for disjunctive ASP on the program's rule structure (incidence graph). First, we provide a polynomial kernel to obtain single-exponential runtime in terms of vertex cover size, despite subset-minimization being not represented in the program's structure. Then we turn our attention to strictly better structural parameters between vertex cover size and treewidth. Here, we provide double-exponential lower bounds for the most prominent parameters in that range: treedepth, feedback vertex size, and cliquewidth. Based on this, we argue that unfortunately our options beyond vertex cover size are limited. Our results provide an in-depth hardness study, relying on a novel reduction from normal to disjunctive programs, trading the increase of complexity for an exponential parameter compression.

Related papers

• 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)
• SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization [67.28453445927825]
  Graph Neural Networks (GNNs) are de facto solutions to structural data learning. Existing graph structure learning (GSL) frameworks still lack robustness and interpretability. This paper proposes a general GSL framework, SE-GSL, through structural entropy and the graph hierarchy abstracted in the encoding tree.
  arXiv  Detail & Related papers  (2023-03-17T05:20:24Z)
• DepGraph: Towards Any Structural Pruning [68.40343338847664]
  We study general structural pruning of arbitrary architecture like CNNs, RNNs, GNNs and Transformers. We propose a general and fully automatic method, emphDependency Graph (DepGraph), to explicitly model the dependency between layers and comprehensively group parameters for pruning. In this work, we extensively evaluate our method on several architectures and tasks, including ResNe(X)t, DenseNet, MobileNet and Vision transformer for images, GAT for graph, DGCNN for 3D point cloud, alongside LSTM for language, and demonstrate that, even with a
  arXiv  Detail & Related papers  (2023-01-30T14:02:33Z)
• Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth? [9.480212602202517]
  This paper deals with a novel reduction from SAT to normal ASP that goes beyond well-known encodings. This characterizes hardness in a fine-grained way by establishing the required functional dependency of the dependency graph's cycle length.
  arXiv  Detail & Related papers  (2023-01-18T12:29:45Z)
• Threshold Treewidth and Hypertree Width [37.90910578253212]
  Treewidth and hypertree width have proven to be highly successful structural parameters in the context of the Constraint Satisfaction (CSP) Here we introduce an enhancement of tree and hypertree width through a novel notion of thresholds. We obtain efficient theoretical as well as empirical algorithms for computing threshold treewidth and hypertree width.
  arXiv  Detail & Related papers  (2022-10-13T13:53:59Z)
• 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)
• MLPruning: A Multilevel Structured Pruning Framework for Transformer-based Models [78.45898846056303]
  Pruning is an effective method to reduce the memory footprint and computational cost associated with large natural language processing models. We develop a novel MultiLevel structured Pruning framework, which uses three different levels of structured pruning: head pruning, row pruning, and block-wise sparse pruning.
  arXiv  Detail & Related papers  (2021-05-30T22:00:44Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  Bilevel optimization has recently attracted growing interests due to its wide applications in modern machine learning problems. We show that our results are more challenging than that of minimax applications.
  arXiv  Detail & Related papers  (2021-02-07T21:46:29Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)
• Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
  Epistemic logic programs (ELPs) are a popular generalization of standard Answer Set Programming (ASP) We show that central problems can be solved in linear time for ELPs exhibiting structural properties in terms of bounded treewidth. We also provide a full dynamic programming algorithm that adheres to these bounds.
  arXiv  Detail & Related papers  (2020-01-13T13:16:13Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.