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

On Turn-Regular Orthogonal Representations

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2022年第3期26卷 285-296页

作者： Bekos, Michael A. Binucci, Carla Di Battista, Giuseppe Didimo, Walter Gronemann, Martin Klein, Karsten Patrignani, Maurizio Rutter, Ignaz Department of Mathematics University of Ioannina Ioannina Greece Department of Engineering University of Perugia Perugia Italy Department of Engineering Roma Tre University Italy Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer and Information Science University of Konstanz Konstanz Germany Department of Computer Science and Mathematics University of Passau Germany

An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other" inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast, finding a minimum-area drawing of H is NP-hard if H is non-turn-regular. This scenario naturally motivates the study of which graphs admit turn-regular orthogonal representations. In this paper we identify notable classes of biconnected planar graphs that always admit such repre-sentations, which can be computed in linear time. We also describe a linear-time testing algorithm for trees and provide a polynomial-time algorithm that tests whether a bi-connected plane graph with "small" faces has a turn-regular orthogonal representation without bends. © 2022, Brown University. All rights reserved.

关键词： Trees (mathematics)

A Structural complexity Analysis of Synchronous Dynamical Systems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Korchemna, Viktoriia Department of Computer Science Royal Holloway University of London United Kingdom Algorithms and Complexity Group TU Wien Austria Eindhoven University of Technology Netherlands

Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dynamic systems: whether the system will transition to a target configuration from a starting configuration, whether the system will reach convergence from a starting configuration, and whether the system is guaranteed to converge from every possible starting configuration. While all three problems were known to be intractable in the classical sense, we initiate the study of their exact boundaries of tractability from the perspective of structural parameters of the network by making use of the more fine-grained parameterized complexity paradigm. As our first result, we consider treewidth—as the most prominent and ubiquitous structural parameter—and show that all three problems remain intractable even on instances of constant treewidth. We complement this negative finding with fixed-parameter algorithms for the former two problems parameterized by treedepth, a well-studied restriction of treewidth. While it is possible to rule out a similar algorithm for convergence guarantee under treedepth, we conclude with a fixed-parameter algorithm for this last problem when parameterized by treedepth and the maximum in-degree. © 2023, CC BY.

关键词： Parameterization

Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time 40

学校读者我要写书评

暂无评论

Fully Dynamic Maximum Independent Sets of Disks in Polylogar...

40th International Symposium on Computational Geometry, SoCG 2024

作者： Bhore, Sujoy Nöllenburg, Martin Tóth, Csaba D. Wulms, Jules Department of Computer Science and Engineering Indian Institute of Technology Bombay Mumbai India Institute of Logic and Computation Algorithms and Complexity Group TU Wien Austria Department of Mathematics California State University Northridge Los AngelesCA United States Department of Computer Science Tufts University MedfordMA United States Department of Mathematics and Computer Science TU Eindhoven Netherlands

ISBN: (纸本)9783959773164

A fundamental question is whether one can maintain a maximum independent set (MIS) in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. For a set of intervals, it is known that no dynamic algorithm can maintain an exact MIS in sublinear update time. Therefore, the typical objective is to explore the trade-off between update time and solution size. Substantial efforts have been made in recent years to understand this question for various families of geometric objects, such as intervals, hypercubes, hyperrectangles, and fat objects. We present the first fully dynamic approximation algorithm for disks of arbitrary radii in the plane that maintains a constant-factor approximate MIS in polylogarithmic expected amortized update time. Moreover, for a fully dynamic set of n unit disks in the plane, we show that a 12-approximate MIS can be maintained with worst-case update time O(log n), and optimal output-sensitive reporting. This result generalizes to fat objects of comparable sizes in any fixed dimension d, where the approximation ratio depends on the dimension and the fatness parameter. Further, we note that, even for a dynamic set of disks of unit radius in the plane, it is impossible to maintain O(1 + Ε)-approximate MIS in truly sublinear update time, under standard complexity assumptions. Our results build on two recent technical tools: (i) The MIX algorithm by Cardinal et al. (ESA 2021) that can smoothly transition from one independent set to another;hence it suffices to maintain a family of independent sets where the largest one is an O(1)-approximate MIS. (ii) A dynamic nearest/farthest neighbor data structure for disks by Kaplan et al. (DCG 2020) and Liu (SICOMP 2022), which generalizes the dynamic convex hull data structure by Chan (JACM 2010), and quickly yields a "replacement" disk (if any) when a disk in one of our independent sets is deleted. © Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth, and Jules Wulms.

关键词： Data structures

ALGORITHMIC APPLICATIONS OF TREE-CUT WIDTH

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Ganian, Robert Kim, Eun Jung Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria CNRS Université Paris-Dauphine Paris France

The recently introduced graph parameter tree-cut width plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper, we provide the first algorithmic applications of tree-cut width to hard combinatorial problems. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems that are not known to be fixed-parameter tractable (FPT) when parameterized by treewidth. We introduce the notion of nice tree-cut decompositions and provide FPT algorithms for the showcase problems Capacitated Vertex Cover, Capacitated Dominating Set, and Imbalance parameterized by the tree-cut width of an input graph. On the other hand, we show that List Coloring, Precoloring Extension, and Boolean CSP (the latter parameterized by the tree-cut width of the incidence graph) are W[1]-hard and hence unlikely to be fixed-parameter tractable when parameterized by tree-cut width. Copyright © 2022, The Authors. All rights reserved.

关键词： Integer programming

Counting Vanishing Matrix-Vector Products

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Brand, Cornelius Korchemna, Viktoriia Skotnica, Michael Simonov, Kirill Algorithms and Complexity Group TU Wien Austria Department of Applied Mathematics Charles University Prague Czech Republic Hasso Plattner Institute University of Potsdam Germany

Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let v ∈ Qd be a rational vector, (T1, T2 . . . Tm) a list of d × d rational matrices, S ∈ Qh×d a rational matrix not necessarily square and k a parameter. The goal is to compute the number of ways one can choose k matrices Ti1 , Ti2 , . . ., Tik from the list such that STik · · · Ti1 v = 0 ∈ Qh. In this paper, we show that this problem is #W[2]-hard for parameter k. As a consequence, computing the k-th homotopy group of a d-dimensional 1-connected topological space for d > 3 is #W[2]-hard for parameter k. We also discuss a decision version of the problem and its several modifications for which we show W[1]/W[2]-hardness. This is in contrast to the parameterized k-sum problem, which is only W[1]-hard (Abboud-Lewi-Williams, ESA’14). In addition, we show that the decision version of the problem without parameter is an undecidable problem, and we give a fixed-parameter tractable algorithm for matrices of bounded size over finite fields, parameterized the matrix dimensions and the order of the field. Copyright © 2023, The Authors. All rights reserved.

关键词： Matrix algebra

Parameterised Partially-Predrawn Crossing Number

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Hamm, Thekla Hliněný, Petr Algorithms and Complexity Group TU Wien Vienna Austria Faculty of Informatics Masaryk University Brno Czech Republic

Inspired by the increasingly popular research on extending partial graph drawings, we propose a new perspective on the traditional and arguably most important geometric graph parameter, the crossing number. Specifically, we define the partially predrawn crossing number to be the smallest number of crossings in any drawing of a graph, part of which is prescribed on the input (not counting the prescribed crossings). Our main result - an FPT-algorithm to compute the partially predrawn crossing number - combines advanced ideas from research on the classical crossing number and so called partial planarity in a very natural but intricate way. Not only do our techniques generalise the known FPT-algorithm by Grohe for computing the standard crossing number, they also allow us to substantially improve a number of recent parameterised results for various drawing extension *** Codes 68R10, 68U05 Copyright © 2022, The Authors. All rights reserved.

关键词： Parameterization

The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k ≥ 5

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Heimann, Sophia Hoang, Hung P. Hougardy, Stefan Research Institute for Discrete Mathematics University of Bonn Germany Algorithms and Complexity Group Faculty of Informatics TU Wien Austria Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics University of Bonn Germany

The k-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most k edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the k-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the k-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires k 1000 and has a substantial gap. We show the two properties above for a much smaller value of k, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for k ≥ 17 and the exponential running time for k ≥ *** Codes 68W25, 68W40, 68Q25, 90C27 © 2024, CC BY-NC-ND.

关键词： Traveling salesman problem

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)