检索结果-内蒙古大学图书馆

A Dynamic MaxSAT-based Approach to Directed Feedback Vertex Sets

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Kiesel, Rafael Schidler, André Institute of Logic and Computation Tu Wien Vienna Austria Algorithms and Complexity Group Tu Wien Vienna Austria

We propose a new approach to the Directed Feedback Vertex Set Problem (DFVSP), where the input is a directed graph and the solution is a minimum set of vertices whose removal makes the graph acyclic. Our approach, implemented in the solver DAGer, is based on two novel contributions: Firstly, we add a wide range of data reductions that are partially inspired by reductions for the similar vertex cover problem. For this, we give a theoretical basis for lifting reductions from vertex cover to DFVSP but also incorporate novel ideas into strictly more general and new DFVSP reductions. Secondly, we propose dynamically encoding DFVSP in propositional logic using cycle propagation for improved performance. Cycle propagation builds on the idea that already a limited number of the constraints in a propositional encoding is usually sufficient for finding an optimal solution. Our algorithm, therefore, starts with a small number of constraints and cycle propagation adds additional constraints when necessary. We propose an efficient integration of cycle propagation into the workflow of MaxSAT solvers, further improving the performance of our algorithm. Our extensive experimental evaluation shows that DAGer significantly outperforms the state-of-the-art solvers and that our data reductions alone directly solve many of the instances. Copyright © 2022, The Authors. All rights reserved.

关键词： Directed graphs

The Computational complexity of Concise Hypersphere Classification

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Royal Holloway University of London United Kingdom Algorithms and Complexity Group TU Wien Austria DePaul University United States University of Leeds United Kingdom

Hypersphere classification is a classical and foundational method that can provide easy-to-process explanations for the classification of real-valued and binary data. However, obtaining an (ideally concise) explanation via hypersphere classification is much more difficult when dealing with binary data than real-valued data. In this paper, we perform the first complexity-theoretic study of the hypersphere classification problem for binary data. We use the fine-grained parameterized complexity paradigm to analyze the impact of structural properties that may be present in the input data as well as potential conciseness constraints. Our results include stronger lower bounds and new fixed-parameter algorithms for hypersphere classification of binary data, which can find an exact and concise explanation when one exists. © 2023, CC BY.

关键词： Classification (of information)

LACON-, SHRUB- AND PARITY-DECOMPOSITIONS: CHARACTERIZING TRANSDUCTIONS OF BOUNDED EXPANSION CLASSES

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Dreier, Jan Algorithms and Complexity Group TU Wien Austria

The concept of bounded expansion provides a robust way to capture sparse graph classes with interesting algorithmic properties. Most notably, every problem definable in first-order logic can be solved in linear time on bounded expansion graph classes. First-order interpretations and transductions of sparse graph classes lead to more general, dense graph classes that seem to inherit many of the nice algorithmic properties of their sparse counterparts. In this paper, we show that one can encode graphs from a class with structurally bounded expansion via lacon-, shrub- and parity-decompositions from a class with bounded expansion. These decompositions are useful for lifting properties from sparse to structurally sparse graph classes. © 2021, CC BY.

关键词： Expansion

Crossing-optimal extension of simple drawings 48

学校读者我要写书评

暂无评论

Crossing-optimal extension of simple drawings

48th International Colloquium on Automata, Languages, and Programming, ICALP 2021

作者： Ganian, Robert Hamm, Thekla Klute, Fabian Parada, Irene Vogtenhuber, Birgit Algorithms and Complexity Group TU Wien Austria Deptartment of Information and Computing Sciences Utrecht University Netherlands TU Eindhoven Netherlands Graz University of Technology Austria

ISBN: (纸本)9783959771955

In extension problems of partial graph drawings one is given an incomplete drawing of an input graph G and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, the extension problem of simple drawings has only recently been shown to be NP-hard even for inserting a single edge. In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for k-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing. © 2021 Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, and Birgit Vogtenhuber.

关键词： Drawing (graphics)

A Unifying Framework for Characterizing and Computing Width Measures 13

学校读者我要写书评

暂无评论

A Unifying Framework for Characterizing and Computing Width ...

13th Innovations in Theoretical Computer Science Conference, ITCS 2022

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Jaffke, Lars Kwon, O-Joung Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria Department of Informatics University of Bergen Norway Department of Mathematics Incheon National University Korea Republic of Discrete Mathematics Group Institute for Basic Science Daejeon Korea Republic of

ISBN: (纸本)9783959772174

algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify F-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of F-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can approximate every possible F-branchwidth, providing a unifying parameterized framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions. © Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon;licensed under Creative Commons License CC-BY 4.0

关键词： Parameter estimation

Finding a Cluster in Incomplete Data 30

学校读者我要写书评

暂无评论

Finding a Cluster in Incomplete Data

30th Annual European Symposium on algorithms, ESA 2022

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria School of Computing DePaul University ChicagoIL United States University of Leeds School of Computing Leeds United Kingdom

ISBN: (纸本)9783959772471

We study two variants of the fundamental problem of finding a cluster in incomplete data. In the problems under consideration, we are given a multiset of incomplete d-dimensional vectors over the binary domain and integers k and r, and the goal is to complete the missing vector entries so that the multiset of complete vectors either contains (i) a cluster of k vectors of radius at most r, or (ii) a cluster of k vectors of diameter at most r. We give tight characterizations of the parameterized complexity of the problems under consideration with respect to the parameters k, r, and a third parameter that captures the missing vector entries. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Vectors

Learning fast-inference Bayesian networks 21

学校读者我要写书评

暂无评论

Learning fast-inference Bayesian networks

Proceedings of the 35th International Conference on Neural Information Processing Systems

作者： Vaidyanathan Peruvemba Ramaswamy Stefan Szeider Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9781713845393

We propose new methods for learning Bayesian networks (BNs) that reliably support fast inference. We utilize maximum state space size as a more fine-grained measure for the BN's reasoning complexity than the standard treewidth measure, thereby accommodating the possibility that variables range over domains of different sizes. Our methods combine heuristic BN structure learning algorithms with the recently introduced MaxSAT-powered local improvement method (Peruvemba Ramaswamy and Szeider, AAAI'21). Our experiments show that our new learning methods produce BNs that support significantly faster exact probabilistic inference than BNs learned with treewidth bounds.

关键词：

A SAT Approach to Twin-Width

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Schidler, André Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria

The graph invariant twin-width was recently introduced by Bonnet, Kim, Thomassé, and Watrigan. Problems expressible in first-order logic, which includes many prominent NP-hard problems, are tractable on graphs of bounded twin-width if a certificate for the twin-width bound is provided as an input. Computing such a certificate, however, is an intrinsic problem, for which no nontrivial algorithm is known. In this paper, we propose the first practical approach for computing the twin-width of graphs together with the corresponding certificate. We propose efficient SAT-encodings that rely on a characterization of twin-width based on elimination sequences. This allows us to determine the twin-width of many famous graphs with previously unknown twin-width. We utilize our encodings to identify the smallest graphs for a given twin-width bound d ∈ {1, . . ., 4}. Copyright © 2021, The Authors. All rights reserved.

关键词： Encoding (symbols)

Self-organized transport in noisy dynamic networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Folz, Frederic Mehlhorn, Kurt Morigi, Giovanna Theoretische Physik Universität des Saarlandes Saarbrücken66123 Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarland Informatics Campus Saarbrücken66123 Germany

We present a numerical study of multi-commodity transport in a noisy, nonlinear network. The nonlinearity determines the dynamics of the edge capacities, which can be amplified or suppressed depending on the local current flowing across an edge. We consider network self-organization for three different nonlinear functions: For all three we identify parameter regimes where noise leads to self-organization into more robust topologies, that are not found by the sole noiseless dynamics. Moreover, the interplay between noise and specific functional behavior of the nonlinearity gives rise to different features, such as (i) continuous or discontinuous responses to the demand strength and (ii) either single or multi-stable solutions. Our study shows the crucial role of the activation function on noise-assisted phenomena. © 2024, CC BY-NC-SA.

关键词： Nonlinear simulations