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

On Erdős–Szekeres-Type Problems for k-convex Point Sets 1

学校读者我要写书评

暂无评论

30th International Workshop on Combinatorial algorithms, IWOCA 2019

作者： Balko, Martin Bhore, Sujoy Martínez Sandoval, Leonardo Valtr, Pavel Department of Applied Mathematics Charles University Prague Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria Sorbonne Université Paris France

ISBN: (数字)9783030250058

ISBN: (纸本)9783030250041

We study Erdős–Szekeres-type problems for k-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set S of n points is k-convex if there exists a spanning simple polygonization of S such that the intersection of any straight line with its interior consists of at most k connected components. We address several open problems about k-convex point sets. In particular, we extend the well-known Erdős–Szekeres Theorem by showing that, for every fixed k ∈ N, every set of n points in the plane in general position (with no three collinear points) contains a k-convex subset of size at least Ω(logk n). We also show that there are arbitrarily large 3-convex sets of n points in the plane in general position whose largest 1-convex subset has size O(log n). This gives a solution to a problem posed by Aichholzer et al.Â [2]. We prove that there is a constant c > 0 such that, for every n ∈ N, there is a set S of n points in the plane in general position such that every 2-convex polygon spanned by at least c · log n points from S contains a point of S in its interior. This matches an earlier upper bound by Aichholzer et al.Â [2] upÂ to a multiplicative constant and answers another of their open problems. © 2019, Springer Nature Switzerland AG.

关键词： Geometry

Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Brand, Cornelius Ceylan, Esra Ganian, Robert Hatschka, Christian Korchemna, Viktoriia Algorithms and Complexity Group TU Wien Vienna Austria

Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by treewidth, a natural alternative would be to use a suitable analogue of treewidth that is based on edge cuts instead of vertex separators. While tree-cut width has been coined as such an analogue of treewidth for edge cuts, its algorithmic applications have often led to disappointing results: out of twelve problems where one would hope for fixed-parameter tractability parameterized by an edge-cut based analogue to treewidth, eight were shown to be W[1]-hard parameterized by tree-cut width. As our main contribution, we develop an edge-cut based analogue to treewidth called edge-cut width. Edge-cut width is, intuitively, based on measuring the density of cycles passing through a spanning tree of the graph. Its benefits include not only a comparatively simple definition, but mainly that it has interesting algorithmic properties: it can be computed by a fixed-parameter algorithm, and it yields fixed-parameter algorithms for all the aforementioned problems where tree-cut width failed to do so. © 2022, CC BY.

关键词： Parameterization

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

Independent sets of dynamic rectangles: algorithms and experiments

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

We study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on dynamic sets of O(n) axis-parallel rectangles, which can be modeled as dynamic rectangle intersection graphs. We consider the fully dynamic vertex update (insertion/deletion) model for two types of rectangles: (i) uniform height and width and (ii) uniform height and arbitrary width. These types of dynamic vertex update problems arise, e.g., in interactive map labeling. We present the first deterministic algorithm for maintaining a MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This breaks the natural barrier of O(Δ) update time (where Δ is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate Max-IS with O(1) update time. In a subsequent algorithm, we establish the trade-off between approximation quality 2(1 + 1/k) and update time O(k2log n) for k ∈ . We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of uniform height and arbitrary width rectangles with O(ω log n) update time, where ω is the largest number of maximal cliques stabbed by any axis-parallel line. We have implemented our algorithms and report the results of an experimental comparison exploring the trade-off between solution size and update time for synthetic and real-world map labeling data sets. Copyright © 2020, The Authors. All rights reserved.

关键词： Geometry

The Power of Collaboration: Learning Large Bayesian Networks at Scale

学校读者我要写书评

暂无评论

The Power of Collaboration: Learning Large Bayesian Networks...

International Conference on Tools for Artificial Intelligence (ICTAI)

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

ISBN: (数字)9798331527235

ISBN: (纸本)9798331527242

We present a novel approach to learn the structure of large Bayesian Networks (BNs) of bounded treewidth. Our approach combines the complementary strengths of heuristic and MaxSAT-based methods. Both methods operate in parallel and cooperate in a mutually advantageous way to improve the quality of the learned BN structures. Our work utilizes an approach proposed by Peruvemba Ramaswamy and Szeider (AAAI'21, NeurIPS'21, UAI'22), which continually applies a MaxSAT-based algorithm to a BN obtained from heuristic search. We create a continuous and dynamic refinement process by allowing the heuristic and the MaxSAT-based technique to cooperate and repeatedly share their work. Our rigorous experiments show that the collaboration between the two methods is a powerful strategy for increasing the score of the learned BN structure. Moreover, the rate at which the score increases is significantly higher than that of the individual methods by themselves. Our results provide a strong argument for combining complementary approaches to learn treewidth-bounded BNs in a collaborative way.

关键词： Image color analysis Heuristic algorithms Collaboration Real-time systems Bayes methods Relays Artificial intelligence Tuning Optimization Bars

The Parameterized complexity Landscape of the Unsplittable Flow Problem

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ganian, Robert Rocton, Mathis Unterberger, Daniel Algorithms and Complexity Group TU Wien Vienna Austria

We study the well-established problem of finding an optimal routing of unsplittable flows in a graph. While by now there is an extensive body of work targeting the problem on graph classes such as paths and trees, we aim at using the parameterized paradigm to identify its boundaries of tractability on general graphs. We develop novel algorithms and lower bounds which result in a full classification of the parameterized complexity of the problem with respect to natural structural parameterizations for the problem—notably maximum capacity, treewidth, maximum degree, and maximum flow length. In particular, we obtain a fixed-parameter algorithm for the problem when parameterized by all four of these parameters, establish XP-tractability as well as W[1]hardness with respect to the former three and latter three parameters, and all remaining cases remain paraNP-hard. © 2024, CC BY.

关键词：

PACE Solver Description: Touiouidth 18

学校读者我要写书评

暂无评论

PACE Solver Description: Touiouidth

18th International Symposium on Parameterized and Exact Computation, IPEC 2023

作者： Berthe, Gaétan Coudert-Osmont, Yoann Dobler, Alexander Morelle, Laure Reinald, Amadeus Rocton, Mathis LIRMM CNRS Université de Montpellier France Université de Lorraine CNRS Inria LORIA France Algorithms and Complexity Group TU Wien Austria

We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++... 详细信息

ISBN: (纸本)9783959773058

关键词： Branch and bound method

Co-Certificate Learning with SAT Modulo Symmetries

学校读者我要写书评

暂无评论

arXiv 2023年

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

We present a new SAT-based method for generating all graphs up to isomorphism that satisfy a given co-NP property. Our method extends the SAT Modulo Symmetry (SMS) framework with a technique that we call co-certificate learning. If SMS generates a candidate graph that violates the given co-NP property, we obtain a certificate for this violation, i.e., ‘co-certificate’ for the co-NP property. The co-certificate gives rise to a clause that the SAT solver, serving as SMS’s backend, learns as part of its CDCL procedure. We demonstrate that SMS plus co-certificate learning is a powerful method that allows us to improve the best-known lower bound on the size of Kochen-Specker vector systems, a problem that is central to the foundations of quantum mechanics and has been studied for over half a century. Our approach is orders of magnitude faster and scales significantly better than a recently proposed SAT-based method. Copyright © 2023, The Authors. All rights reserved.

关键词： Quantum theory

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)