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

arXiv 2025年

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Sridharan, Ramanujan M. Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Vienna Austria School of Computing DePaul University Chicago United States Department of Computer Science University of Warwick United Kingdom

We study a variant of the Coordinated Motion Planning problem on undirected graphs, referred to herein as the Coordinated Sliding-Motion Planning (CSMP) problem. In this variant, we are given an undirected graph G, k robots R1, . . ., Rk positioned on distinct vertices of G, p ≤ k distinct destination vertices for robots R1, . . ., Rp, and ∈ . The problem is to decide if there is a serial schedule of at most moves (i.e., of makespan ) such that at the end of the schedule each robot with a destination reaches it, where a robot’s move is a free path (unoccupied by any robots) from its current position to an unoccupied vertex. The problem is known to be NP-hard even on full grids. It has been studied in several contexts, including coin movement and reconfiguration problems, with respect to feasibility, complexity, and approximation. Geometric variants of the problem, in which congruent geometric-shape robots (e.g., unit disk/squares) slide or translate in the Euclidean plane, have also been studied extensively. We investigate the parameterized complexity of CSMP with respect to two parameters: the number k of robots and the makespan . As our first result, we present a fixed-parameter algorithm for CSMP parameterized by k. For our second result, we present a fixed-parameter algorithm parameterized by for the special case of CSMP in which only a single robot has a destination and the graph is planar, which we prove to be NP-complete. A crucial new ingredient for both of our results is that the solution admits a succinct representation as a small labeled topological minor of the input graph. © 2025, CC BY-NC-ND.

关键词： Undirected graphs

来源：评论

学校读者我要写书评

暂无评论

Segment Intersection Representations, Level Planarity and Constrained Ordering Problems

arXiv

引用

arXiv 2025年

作者： Fink, Simon D. Pfretzschner, Matthias Stumpf, Peter Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Computer Science and Mathematics University of Passau Germany Department of Theoretical Computer Science Faculty of Information Technology Czech Technical University Prague Czech Republic Department of Applied Mathematics Charles University Prague Czech Republic

In the Segment Intersection Graph Representation Problem, we want to represent the vertices of a graph as straight line segments in the plane such that two segments cross if and only if there is an edge between the corresponding vertices. This problem is NP-hard (even ∃R-complete [19]) in the general case [13] and remains so if we restrict the segments to be axis-aligned, i.e., horizontal and vertical [12]. A long standing open question for the latter variant is its complexity when the order of segments along one axis (say the vertical order of horizontal segments) is already given [12,14]. We resolve this question by giving efficient solutions using two very different approaches that are interesting on their own. First, using a graph-drawing perspective, we relate the problem to a variant of the well-known Level Planarity problem, where vertices have to lie on preassigned horizontal levels. In our case, each level also carries consecutivity constraints on its vertices;this Level Planarity variant is known to have a quadratic solution. Second, we use an entirely combinatorial approach and show that both problems can equivalently be formulated as a linear ordering problem subject to certain consecutivity constraints. While the complexity of such problems varies greatly, we show that in this case the constraints are well-structured in a way that allows a direct quadratic solution. Thus, we obtain three different-but-equivalent perspectives on this problem: the initial geometric one, one from planar graph drawing and a purely combinatorial one. © 2025, CC BY.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

SAT Backdoors: Depth Beats Size 30

SAT Backdoors: Depth Beats Size

引用

30th Annual European Symposium on algorithms, ESA 2022

作者： Dreier, Jan Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Austria Algorithms and Complexity Group University of Leeds United Kingdom

ISBN: (纸本)9783959772471

For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time tractability of Horn formulas (Aspvall, Plass, and Tarjan, 1979) and Krom (i.e., 2CNF) formulas (Dowling and Gallier, 1984). Backdoors, introduced by Williams, Gomes and Selman (2003), gradually extend such a tractable class to all formulas of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a formula and a tractable class. Backdoor depth, introduced by Mählmann, Siebertz, and Vigny (2021), is a more refined distance measure, which admits the utilization of different backdoor variables in parallel. Bounded backdoor size implies bounded backdoor depth, but there are formulas of constant backdoor depth and arbitrarily large backdoor size. We propose FPT approximation algorithms to compute backdoor depth into the classes Horn and Krom. This leads to a linear-time algorithm for deciding the satisfiability of formulas of bounded backdoor depth into these classes. We base our FPT approximation algorithm on a sophisticated notion of obstructions, extending Mählmann et al.'s obstruction trees in various ways, including the addition of separator obstructions. We develop the algorithm through a new game-theoretic framework that simplifies the reasoning about backdoors. Finally, we show that bounded backdoor depth captures tractable classes of CNF formulas not captured by any known method. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

CSP Beyond Tractable Constraint Languages 28

CSP Beyond Tractable Constraint Languages

引用

28th International Conference on Principles and Practice of Constraint Programming, CP 2022

作者： Dreier, Jan Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Austria Algorithms and Complexity Group University of Leeds United Kingdom

ISBN: (纸本)9783959772402

The constraint satisfaction problem (CSP) is among the most studied computational problems. While NP-hard, many tractable subproblems have been identified (Bulatov 2017, Zuk 2017). Backdoors, introduced by Williams, Gomes, and Selman (2003), gradually extend such a tractable class to all CSP instances of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a CSP instance and a tractable class. Backdoor depth, introduced by Mählmann, Siebertz, and Vigny (2021) for SAT, is a more refined distance measure, which admits the parallel utilization of different backdoor variables. Bounded backdoor size implies bounded backdoor depth, but there are instances of constant backdoor depth and arbitrarily large backdoor size. Dreier, Ordyniak, and Szeider (2022) provided fixed-parameter algorithms for finding backdoors of small depth into the classes of Horn and Krom formulas. In this paper, we consider backdoor depth for CSP. We consider backdoors w.r.t. tractable subproblems CΓ of the CSP defined by a constraint language Γ, i.e., where all the constraints use relations from the language Γ. Building upon Dreier et al.’s game-theoretic approach and their notion of separator obstructions, we show that for any finite, tractable, semi-conservative constraint language Γ, the CSP is fixed-parameter tractable parameterized by the backdoor depth into CΓ plus the domain size. With backdoors of low depth, we reach classes of instances that require backdoors of arbitrary large size. Hence, our results strictly generalize several known results for CSP that are based on backdoor size. © Jan Dreier, Sebastian Ordyniak, and Stefan Szeider.

关键词： Constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

MosaicSets: Embedding Set Systems into Grid Graphs

引用

IEEE Transactions on Visualization and Computer Graphics 2023年第1期29卷 875-885页

作者： Rottmann, Peter Wallinger, Markus Bonerath, Annika Gedicke, Sven Nollenburg, Martin Haunert, Jan-Henrik Geoinformation Group University of Bonn Germany Algorithms and Complexity Group Technical University of Vienna Austria

Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets: a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews. © 2022 IEEE.

关键词： Visualization

来源：评论

学校读者我要写书评

暂无评论

Searching for Smallest Universal Graphs and Tournaments with SAT 29

Searching for Smallest Universal Graphs and Tournaments with...

引用

29th International Conference on Principles and Practice of Constraint Programming, CP 2023

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

ISBN: (纸本)9783959773003

A graph is induced k-universal if it contains all graphs of order k as an induced subgraph. For over half a century, the question of determining smallest k-universal graphs has been studied. A related question asks for a smallest k-universal tournament containing all tournaments of order k. This paper proposes and compares SAT-based methods for answering these questions exactly for small values of k. Our methods scale to values for which a generate-and-test approach isn't feasible;for instance, we show that an induced 7-universal graph has more than 16 vertices, whereas the number of all connected graphs on 16 vertices, modulo isomorphism, is a number with 23 decimal digits Our methods include static and dynamic symmetry breaking and lazy encodings, employing external subgraph isomorphism testing. © Tianwei Zhang and Stefan Szeider.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Computing Small Rainbow Cycle Numbers with SAT Modulo Symmetries 30

Computing Small Rainbow Cycle Numbers with SAT Modulo Symmet...

引用

30th International Conference on Principles and Practice of Constraint Programming, CP 2024

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

ISBN: (纸本)9783959773362

Envy-freeness up to any good (EFX) is a key concept in Computational Social Choice for the fair division of indivisible goods, where no agent envies another's allocation after removing any single item. A deeper understanding of EFX allocations is facilitated by exploring the rainbow cycle number (Rf (d)), the largest number of independent sets in a certain class of directed graphs. Upper bounds on Rf (d) provide guarantees to the feasibility of EFX allocations (Chaudhury et al., EC 2021). In this work, we precisely compute the numbers Rf (d) for small values of d, employing the SAT modulo Symmetries framework (Kirchweger and Szeider, CP 2021). SAT modulo Symmetries is tailored specifically for the constraint-based isomorph-free generation of combinatorial structures. We provide an efficient encoding for the rainbow cycle number, comparing eager and lazy approaches. To cope with the huge search space, we extend the encoding with invariant pruning, a new method that significantly speeds up computation. © Markus Kirchweger and Stefan Szeider.

关键词： Encoding (symbols)

来源：评论

学校读者我要写书评

暂无评论

Slim Tree-Cut Width 17

Slim Tree-Cut Width

引用

17th International Symposium on Parameterized and Exact Computation, IPEC 2022

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

ISBN: (纸本)9783959772600

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 an approximation algorithm for computing the parameter. © Robert Ganian and Viktoriia Korchemna.

关键词： Structural properties

来源：评论

学校读者我要写书评

暂无评论

The Parameterized complexity Of Extending Stack Layouts 32

The Parameterized Complexity Of Extending Stack Layouts

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

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

ISBN: (纸本)9783959773430

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 complexity-theoretic 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. © Thomas Depian, Simon D. Fink, Robert Ganian, and Martin Nöllenburg.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Small Unsatisfiable k-CNFs with Bounded Literal Occurrence 27

Small Unsatisfiable k-CNFs with Bounded Literal Occurrence

引用

27th International Conference on Theory and Applications of Satisfiability Testing, SAT 2024

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

ISBN: (纸本)9783959773348

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. © Tianwei Zhang, Tomáš Peitl, and Stefan Szeider.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：