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

Untangling Circular Drawings: algorithms and complexity

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Vienna Austria University of Passau Passau Germany Research Unit of Computer Graphics TU Wien Vienna Austria St. Pölten University of Applied Sciences St. Pölten Austria

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G = (V, E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift◦(δG) as the minimum number of vertices that are required to be shifted in order to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift◦(δG) ≤ K for a given integer K, is NP-complete. For n-vertex outerplanar graphs, we obtain a tight upper bound of shift◦(δG) ≤ n − ⌊√n − 2⌋ − 2. Moreover, we study the Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. For this problem, we provide a tight upper bound shift◦(δG) ≤ ⌊n/2⌋ − 1 and present a constructive polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. © 2021, CC BY.

关键词： Drawing (graphics)

Large and Parallel Human Sorting Networks 7th

学校读者我要写书评

暂无评论

Large and Parallel Human Sorting Networks

7th International Conference on Creative Mathematical Sciences Communication, CMSC 2024

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

ISBN: (纸本)9783031732560

This paper presents two innovative extensions of the classic Human Sorting Network (HSN) activity from the CS Unplugged program. First, we describe the implementation of a large-scale HSN with 50 input nodes, realized with high school students in Vienna, Austria. We detail the logistical challenges and solutions for creating an HSN of this magnitude, including location selection, network layout, and participant coordination. Second, we report on using parallel 6-input HSNs, which introduce a competitive element and enhance engagement. This parallel setup allows for races between teams and can be adapted for various age groups and knowledge levels. Both extensions aim to increase the educational impact and enjoyment of the HSN activity. We provide comprehensive insights into our experiences, enabling other educators and researchers to replicate or further develop these HSN variants. © The Author(s) 2025.

关键词： algorithmic education Computational Thinking CS Unplugged Human sorting networks large-scale computing activities parallel sorting algorithms

A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-Like Multigraphs 42

学校读者我要写书评

暂无评论

A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-...

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Ghorbani, Ebrahim Hoff, Jonah Leander Mnich, Matthias Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

ISBN: (纸本)9783959773652

Propp machines, or rotor-router models, are a classic tool to simulate random systems in forms of Markov chains by deterministic systems. To this end, the nodes of the Markov chain are replaced by switching nodes, which maintain a queue over their outgoing arcs, and a particle sent through the system traverses the top arc of the queue which is then moved to the end of the queue and the particle arrives at the next node. A key question to answer about such systems is whether a single particle can reach a particular target node, given as input an initial configuration of the queues at all switching nodes. This question was introduced by Dohrau et al. (2017) under the name of Arrival. A major open question is whether Arrival can be solved in polynomial time, as it is known to lie in NP ∩ co-NP;yet the fastest known algorithm for general instances takes subexponential time (Gärtner et al., ICALP 2021). We consider a generalized version of Arrival introduced by Auger et al. (RP 2023), which requires routing multiple (potentially exponentially many) particles through a rotor graph. The Multi-Arrival problem is to determine the particle configuration that results from moving all particles from a given initial configuration to sinks. Auger et al. showed that for path-like rotor graphs with a certain uniform rotor order, the problem can be solved in polynomial time. Our main result is a quasi-polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs for arbitrary rotor orders. Tree-like rotor graphs are directed multigraphs which can be obtained from undirected trees by replacing each edge by an arbitrary number of arcs in either or both directions. For trees of bounded contracted height, such as paths, the algorithm runs in polynomial time and thereby generalizes the result by Auger et al.. Moreover, we give a polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs without parallel arcs. © Ebrahim Ghorbani, Jonah Leander Hoff, and Matthias Mnich.

关键词： Chains

The Computational complexity of Positive Non-Clashing Teaching in Graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Ganian, Robert Khazaliya, Liana Inerney, Fionn Mc Rocton, Mathis Algorithms and Complexity Group TU Wien Austria Telefónica Scientific Research Barcelona Spain

We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per concept required to successfully teach an intelligent learner under the considered, previously established model. For any class of concepts, it is known that this problem can be effortlessly transferred to the setting of balls in a graph G. We establish (1) the NP-hardness of the problem even when restricted to instances with positive non-clashing teaching dimension k = 2 and where all balls in the graph are present, (2) near-tight running time upper and lower bounds for the problem on general graphs, (3) fixed-parameter tractability when parameterized by the vertex integrity of G, and (4) a lower bound excluding fixed-parameter tractability when parameterized by the feedback vertex number and pathwidth of G, even when combined with k. Our results provide a nearly complete understanding of the complexity landscape of computing the positive non-clashing teaching dimension and answer open questions from the literature. Copyright © 2025, The Authors. All rights reserved.

关键词： Graph theory

The complexity of Extending Fair Allocations of Indivisible Goods

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Deligkas, Argyrios Eiben, Eduard Ganian, Robert Goldsmith, Tiger-Lily Ioannidis, Stavros D. Department of Computer Science Royal Holloway University of London United Kingdom Algorithms and Complexity group TU Wien Austria

We initiate the study of computing envy-free allocations of indivisible items in the extension setting, i.e., when some part of the allocation is fixed and the task is to allocate the remaining items. Given the known NP-hardness of the problem, we investigate whether—and under which conditions—one can obtain fixed-parameter algorithms for computing a solution in settings where most of the allocation is already fixed. Our results provide a broad complexity-theoretic classification of the problem which includes: (a) fixed-parameter algorithms tailored to settings with few distinct types of agents or items;(b) lower bounds which exclude the generalization of these positive results to more general settings. We conclude by showing that—unlike when computing allocations from scratch—the non-algorithmic question of whether more relaxed EFX allocations exist can be completely resolved in the extension *** Codes 91B32 Copyright © 2025, The Authors. All rights reserved.

关键词：

A Simple Partially Embedded Planarity Test Based on Vertex-Addition 8

学校读者我要写书评

暂无评论

A Simple Partially Embedded Planarity Test Based on Vertex-A...

8th SIAM Symposium on Simplicity of algorithms, SOSA 2025

作者： Fink, Simon D. Rutter, Ignaz Sandhya, T.P. Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Informatics and Mathematics University of Passau Germany Stockholm University Department of Mathematics Sweden

ISBN: (纸本)9781611978315

In the Partially Embedded Planarity problem, we are given a graph G together with a topological drawing of a subgraph H of G. The task is to decide whether the drawing can be extended to a drawing of the whole graph such that no two edges cross. Angelini et al. gave a linear-time algorithm for solving this problem in 2010 [1, 2]. While their paper constitutes a significant result, the algorithm described therein is highly complex: it uses several layers of decompositions according to connectivity of both G and H, its description spans more than 30 pages, and can hardly be considered implementable. We give an independent linear-time algorithm that works along the well-known vertex-addition planarity test by Booth and Lueker [5, 6]. We modify the PC-tree as underlying data structure used for representing all planar drawing possibilities in a natural way to also respect the restrictions given by the prescribed drawing of the subgraph H. The testing algorithm and its proof of correctness only require small adaptations from the comparatively much simpler generic planarity test, of which several implementations exist. If the test succeeds, an embedding can be constructed using the same approaches that are used for the generic planarity test. Copyright © 2025 by SIAM.

关键词： Trees (mathematics)

Extracting Problem Structure with LLMs for Optimized SAT Local Search

学校读者我要写书评

暂无评论

arXiv 2025年

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

Local search preprocessing makes Conflict-Driven Clause Learning (CDCL) solvers faster by providing high-quality starting points and modern SAT solvers have incorporated this technique into their preprocessing steps. However, these tools rely on basic strategies that miss the structural patterns in problems. We present a method that applies Large Language Models (LLMs) to analyze Python-based encoding code. This reveals hidden structural patterns in how problems convert into SAT. Our method automatically generates specialized local search algorithms that find these patterns and use them to create strong initial assignments. This works for any problem instance from the same encoding type. Our tests show encouraging results, achieving faster solving times compared to baseline preprocessing systems. Copyright © 2025, The Authors. All rights reserved.

关键词： Encoding (symbols)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously 42

学校读者我要写书评

暂无评论

Approximate Minimum Tree Cover in All Symmetric Monotone Nor...

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Kaul, Matthias Luo, Kelin Mnich, Matthias Röglin, Heiko Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany University of Bonn Germany University at Buffalo NY United States Universität Bonn Germany

ISBN: (纸本)9783959773652

We study the problem of partitioning a set of n objects in a metric space into k clusters V1,..., Vk. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the p-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in Vi, which may serve as a proxy for the cost of traversing all objects in the cluster, for example in the context of Multirobot Coverage as studied by Zheng, Koenig, Kempe, Jain (IROS 2005), but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This problem has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett., 2004) for the setting of minimizing the weight of the largest cluster (i.e., using ∞) as Min-Max Tree Cover, for which they gave a constant-factor approximation algorithm. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. One can consider these as the fixed starting points of some agents that will traverse all points of a cluster. For this setting also we are able to give a polynomial-time algorithm computing a constant-factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single p norm for the objective. © Matthias Kaul, K

关键词： Trees (mathematics)

Smart Cubing for Graph Search: A Comparative Study

学校读者我要写书评

暂无评论

arXiv 2025年

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

Parallel solving via cube-and-conquer is a key method for scaling SAT solvers to hard instances. While cube-and-conquer has proven successful for pure SAT problems, notably the Pythagorean triples conjecture, its application to SAT solvers extended with propagators presents unique challenges, as these propagators learn constraints dynamically during the search. We study this problem using SAT Modulo Symmetries (SMS) as our primary test case, where a symmetry-breaking propagator reduces the search space by learning constraints that eliminate isomorphic graphs. Through extensive experimentation comprising over 10,000 CPU hours, we systematically evaluate different cube-and-conquer variants on three well-studied combinatorial problems. Our methodology combines prerun phases to collect learned constraints, various cubing strategies, and parameter tuning via algorithm configuration and LLM-generated design suggestions. The comprehensive empirical evaluation provides new insights into effective cubing strategies for propagator-based SAT solving, with our best method achieving speedups of 2-3x from improved cubing and parameter tuning, providing an additional 1.5-2x improvement on harder instances. Copyright © 2025, The Authors. All rights reserved.

关键词： Geometry