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

Turbocharging treewidth-bounded Bayesian network structure learning

学校读者我要写书评

暂无评论

arXiv 2020年

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

We present a new approach for learning the structure of a treewidth-bounded Bayesian Network (BN). The key to our approach is applying an exact method (based on MaxSAT) locally, to improve the score of a heuristically computed BN. This approach allows us to scale the power of exact methods-so far only applicable to BNs with several dozens of random variables-to large BNs with several thousands of random variables. Our experiments show that our method improves the score of BNs provided by state-of-the-art heuristic methods, often significantly. Copyright © 2020, The Authors. All rights reserved.

关键词： Random variables

The Parameterized complexity of Extending Stack Layouts

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Depian, Thomas Fink, Simon D. Ganian, Robert Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

An -page stack layout (also known as an -page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into stacks (or pages), such that the endpoints of no two edges on the same stack alternate. We study the problem of extending a given partial -page stack layout into a complete one, which can be seen as a natural generalization of the classical NP-hard problem of computing a stack layout of an input graph from scratch. Given the inherent intractability of the problem, we focus on identifying tractable fragments through the refined lens of parameterized complexity analysis. Our results paint a detailed and surprisingly rich complexitytheoretic landscape of the problem which includes the identification of paraNP-hard, W[1]-hard and XP-tractable, as well as fixed-parameter tractable fragments of stack layout extension via a natural sequence of parameterizations. © 2024, CC BY.

关键词： Graph embeddings

MCP-Solver: Integrating Language Models with Constraint Programming Systems

学校读者我要写书评

暂无评论

arXiv 2024年

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

While Large Language Models (LLMs) perform exceptionally well at natural language tasks, they often struggle with precise formal reasoning and the rigorous specification of problems. We present MCP-Solver, a prototype implementation of the Model Context Protocol that demonstrates the potential for systematic integration between LLMs and constraint programming systems. Our implementation provides interfaces for the creation, editing, and validation of a constraint model. Through an item-based editing approach with integrated validation, the system ensures model consistency at every modification step and enables structured iterative refinement. The system handles concurrent solving sessions and maintains a persistent knowledge base of modeling insights. Initial experiments suggest that this integration can effectively combine LLMs’ natural language understanding with constraint-solving capabilities. Our open-source implementation is proof of concept for integrating formal reasoning systems with LLMs through standardized protocols. While further research is needed to establish comprehensive formal guarantees, this work takes a first step toward principled integration of natural language processing with constraint-based reasoning. Copyright © 2024, The Authors. All rights reserved.

关键词： Constraint programming

On structural parameterizations of the edge disjoint paths problem

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Ganian, Robert Ordyniak, Sebastian Ramanujan, M.S. Algorithms and Complexity group TU Wien Vienna Austria

In this paper we revisit the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our focus lies on structural parameterizations for the problem that allow for efficient (polynomial-time or fpt) algorithms. As our first result, we answer an open question stated in Fleszar, Mnich, and Spoerhase (2016), by showing that the problem can be solved in polynomial time if the input graph has a feedback vertex set of size one. We also show that EDP parameterized by the treewidth and the maximum degree of the input graph is fixed-parameter tractable. Having developed two novel algorithms for EDP using structural restrictions on the input graph, we then turn our attention towards the augmented graph, i.e., the graph obtained from the input graph after adding one edge between every terminal pair. In constrast to the input graph, where EDP is known to remain NP-hard even for treewidth two, a result by Zhou et al. (2000) shows that EDP can be solved in non-uniform polynomial time if the augmented graph has constant treewidth;we note that the possible improvement of this result to an fpt-algorithm has remained open since then. We show that this is highly unlikely by establishing the W[1]-hardness of the problem parameterized by the treewidth (and even feedback vertex set) of the augmented graph. Finally, we develop an fpt-algorithm for EDP by exploiting a novel structural parameter of the augmented graph. Copyright © 2017, The Authors. All rights reserved.

关键词： Parameterization

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.

关键词：

Small unsatisfiable k-CNFs with bounded literal occurrence

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhang, Tianwei Peitl, Tomáš Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria

We obtain the smallest unsatisfiable formulas in subclasses of k-CNF (exactly k distinct literals per clause) with bounded variable or literal occurrences. Smaller unsatisfiable formulas of this type translate into stronger inapproximability results for MaxSAT in the considered formula class. Our results cover subclasses of 3-CNF and 4-CNF;in all subclasses of 3-CNF we considered we were able to determine the smallest size of an unsatisfiable formula;in the case of 4-CNF with at most 5 occurrences per variable we decreased the size of the smallest known unsatisfiable formula. Our methods combine theoretical arguments and symmetry-breaking exhaustive search based on SAT Modulo Symmetries (SMS), a recent framework for isomorph-free SAT-based graph generation. To this end, and as a standalone result of independent interest, we show how to encode formulas as graphs efficiently for SMS. Copyright © 2024, The Authors. All rights reserved.

关键词： Formal logic

学校读者我要写书评

暂无评论

Slim Tree-Cut Width

arXiv 2022年

作者： Ganian, Robert Korchemna, Viktoriia Algorithms and Complexity Group TU Wien Vienna Austria

Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it turned out that tree-cut width falls short as an edge-cut based alternative to treewidth in algorithmic aspects. This has led to the very recent introduction of a simple edge-based parameter called edge-cut width [WG 2022], which has precisely the algorithmic applications one would expect from an analogue of treewidth for edge cuts, but does not have the desired structural properties. In this paper, we study a variant of tree-cut width obtained by changing the threshold for so-called thin nodes in tree-cut decompositions from 2 to 1. We show that this "slim tree-cut width" satisfies all the requirements of an edge-cut based analogue of treewidth, both structural and algorithmic, while being less restrictive than edge-cut width. Our results also include an alternative characterization of slim tree-cut width via an easy-to-use spanning-tree decomposition akin to the one used for edge-cut width, a characterization of slim tree-cut width in terms of forbidden immersions as well as approximation algorithm for computing the *** Codes 68Q27 © 2022, CC BY.

关键词： Structural properties

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)

Maximizing ink in partial edge drawings of k-plane graphs

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Hummel, Matthias Klute, Fabian Nickel, Soeren Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

Partial edge drawing (PED) is a drawing style for non-planar graphs, in which edges are drawn only partially as pairs of opposing stubs on the respective end-vertices. In a PED, by erasing the central parts of edges, all edge crossings and the resulting visual clutter are hidden in the undrawn parts of the edges. In symmetric partial edge drawings (SPEDs), the two stubs of each edge are required to have the same length. It is known that maximizing the ink (or the total stub length) when transforming a straight-line graph drawing with crossings into a SPED is tractable for 2-plane input drawings, but NP-hard for unrestricted inputs. We show that the problem remains NP-hard even for 3-plane input drawings and establish NP-hardness of ink maximization for PEDs of 4-plane graphs. Yet, for k-plane input drawings whose edge intersection graph forms a collection of trees or, more generally, whose intersection graph has bounded treewidth, we present efficient algorithms for computing maximum-ink PEDs and SPEDs. We implemented the treewidth-based algorithms and show a brief experimental evaluation. Copyright © 2019, The Authors. All rights reserved.

关键词： Drawing (graphics)