TY - JOUR A1 - Hecher, Markus T1 - Treewidth-aware reductions of normal ASP to SAT BT - is normal ASP harder than SAT after all? JF - Artificial intelligence N2 - Answer Set Programming (ASP) is a paradigm for modeling and solving problems for knowledge representation and reasoning. There are plenty of results dedicated to studying the hardness of (fragments of) ASP. So far, these studies resulted in characterizations in terms of computational complexity as well as in fine-grained insights presented in form of dichotomy-style results, lower bounds when translating to other formalisms like propositional satisfiability (SAT), and even detailed parameterized complexity landscapes. A generic parameter in parameterized complexity originating from graph theory is the socalled treewidth, which in a sense captures structural density of a program. Recently, there was an increase in the number of treewidth-based solvers related to SAT. While there are translations from (normal) ASP to SAT, no reduction that preserves treewidth or at least keeps track of the treewidth increase is known. In this paper we propose a novel reduction from normal ASP to SAT that is aware of the treewidth, and guarantees that a slight increase of treewidth is indeed sufficient. Further, we show a new result establishing that, when considering treewidth, already the fragment of normal ASP is slightly harder than SAT (under reasonable assumptions in computational complexity). This also confirms that our reduction probably cannot be significantly improved and that the slight increase of treewidth is unavoidable. Finally, 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 decomposition heuristics. Overall, our reduction works better with these heuristics than existing translations. (c) 2021 Elsevier B.V. All rights reserved. KW - Answer set programming KW - Treewidth KW - Parameterized complexity KW - Complexity KW - analysis KW - Tree decomposition KW - Treewidth-aware reductions Y1 - 2022 U6 - https://doi.org/10.1016/j.artint.2021.103651 SN - 0004-3702 SN - 1872-7921 VL - 304 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Phillips, Jonathan D. A1 - Schwanghart, Wolfgang A1 - Heckmann, Tobias T1 - Graph theory in the geosciences JF - Earth science reviews : the international geological journal bridging the gap between research articles and textbooks N2 - Graph theory has long been used in quantitative geography and landscape ecology and has been applied in Earth and atmospheric sciences for several decades. Recently, however, there have been increased, and more sophisticated, applications of graph theory concepts and methods in geosciences, principally in three areas: spatially explicit modeling, small-world networks, and structural models of Earth surface systems. This paper reviews the contrasting goals and methods inherent in these approaches, but focuses on the common elements, to develop a synthetic view of graph theory in the geosciences. Techniques applied in geosciences are mainly of three types: connectivity measures of entire networks; metrics of various aspects of the importance or influence of particular nodes, links, or regions of the network; and indicators of system dynamics based on graph adjacency matrices. Geoscience applications of graph theory can be grouped in five general categories: (1) Quantification of complex network properties such as connectivity, centrality, and clustering; (2) Tests for evidence of particular types of structures that have implications for system behavior, such as small-world or scale-free networks; (3) Testing dynamical system properties, e.g., complexity, coherence, stability, synchronization, and vulnerability; (4) Identification of dynamics from historical records or time series; and (5) spatial analysis. Recent and future expansion of graph theory in geosciences is related to general growth of network-based approaches. However, several factors make graph theory especially well suited to the geosciences: Inherent complexity, exploration of very large data sets, focus on spatial fluxes and interactions, and increasing attention to state transitions are all amenable to analysis using graph theory approaches. (C) 2015 Elsevier B.V. All rights reserved. KW - Graph theory KW - Geosciences KW - Networks KW - Spatially explicit models KW - Structural models KW - Complexity Y1 - 2015 U6 - https://doi.org/10.1016/j.earscirev.2015.02.002 SN - 0012-8252 SN - 1872-6828 VL - 143 SP - 147 EP - 160 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Nikoloski, Zoran A1 - Grimbs, Sergio A1 - Klie, Sebastian A1 - Selbig, Joachim T1 - Complexity of automated gene annotation JF - Biosystems : journal of biological and information processing sciences N2 - Integration of high-throughput data with functional annotation by graph-theoretic methods has been postulated as promising way to unravel the function of unannotated genes. Here, we first review the existing graph-theoretic approaches for automated gene function annotation and classify them into two categories with respect to their relation to two instances of transductive learning on networks - with dynamic costs and with constant costs - depending on whether or not ontological relationship between functional terms is employed. The determined categories allow to characterize the computational complexity of the existing approaches and establish the relation to classical graph-theoretic problems, such as bisection and multiway cut. In addition, our results point out that the ontological form of the structured functional knowledge does not lower the complexity of the transductive learning with dynamic costs - one of the key problems in modern systems biology. The NP-hardness of automated gene annotation renders the development of heuristic or approximation algorithms a priority for additional research. KW - Complexity KW - Gene function prediction KW - External structural measures KW - Transductive learning Y1 - 2011 U6 - https://doi.org/10.1016/j.biosystems.2010.12.003 SN - 0303-2647 VL - 104 IS - 1 SP - 1 EP - 8 PB - Elsevier CY - Oxford ER -