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

SSRN 2023年

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

We introduce backdoor DNFs, as a tool to measure the theoretical hardness of CNF formulas. Like backdoor sets and backdoor trees, backdoor DNFs are defined relative to a tractable class of CNF formulas. Each conjunctive term of a backdoor DNF defines a partial assignment that moves the input CNF formula into the base class. Backdoor DNFs are more expressive and potentially smaller than their predecessors backdoor sets and backdoor trees. We establish the fixed-parameter tractability of the backdoor DNF detection problem. Our results hold for the fundamental base classes Horn and 2CNF, and their combination. We complement our theoretical findings by an empirical study. Our experiments show that backdoor DNFs provide a significant improvement over their predecessors. © 2023, The Authors. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Fixed-Parameter algorithms for Computing Bend-Restricted RAC Drawings of Graphs

引用

Journal of Graph algorithms and Applications 2024年第2期28卷 131-150页

作者： Brand, Cornelius Ganian, Robert Röder, Sebastian Schager, Florian Algorithms and Complexity Group TU Wien Vienna Austria

In a right-angle crossing (RAC) drawing of a graph, each edge is represented as a polyline and edge crossings must occur at an angle of exactly 90◦, where the number of bends on such polylines is typically restricted in some way. While structural and topological properties of RAC drawings have been the focus of extensive research and particular attention has been paid to RAC drawings with at most 0, 1, 2 and 3 bends per edge, little was known about the boundaries of tractability for computing such drawings. In this paper, we initiate the study of bend-restricted RAC drawings from the viewpoint of parameterized complexity. In particular, we establish that computing a RAC drawing of an input graph G with at most b bends where each edge e has a prescribed upper-bound 0 ≤ β(e) ≤ 3 on the number of bends it can support (or determining that none exists) is: • fixed-parameter tractable parameterized by the feedback edge number of G, and • fixed-parameter tractable parameterized by b plus the vertex cover number of G. © 2024, Brown University. All rights reserved.

关键词： Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

SAT backdoors: Depth beats size

arXiv

引用

arXiv 2022年

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

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. Copyright © 2022, The Authors. All rights reserved.

关键词： Clustering algorithms

来源：评论

学校读者我要写书评

暂无评论

Parameterized study of steiner tree on unit disk graphs 17

Parameterized study of steiner tree on unit disk graphs

引用

17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020

作者： Bhore, Sujoy Carmi, Paz Kolay, Sudeshna Zehavi, Meirav Algorithms and Complexity Group TU Wien Austria Ben-Gurion University of the Negev Beersheba Israel Indian Institute of Technology Kharagpur India

ISBN: (纸本)9783959771504

We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R ⊆ V(G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V \R. The vertices of R are referred to as terminals and the vertices of V(G) \R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in nO(√t+k) time. We also show that the Steiner Tree problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2O(k)nO(1). In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [16]. We mention that the algorithmic results can be made to work for Steiner Tree on disk graphs with bounded aspect ratio. Finally, we prove that Steiner Tree on disk graphs parameterized by k is W[1]-hard. © Sujoy Bhore, Paz Carmi, Sudeshna Kolay, and Meirav Zehavi;licensed under Creative Commons License CC-BY

关键词： Aspect ratio

来源：评论

学校读者我要写书评

暂无评论

The complexity of Bayesian network learning: revisiting the superstructure 21

The complexity of Bayesian network learning: revisiting the ...

引用

Proceedings of the 35th International Conference on Neural Information Processing Systems

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

ISBN: (纸本)9781713845393

We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up on previous works that have analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed-parameter tractable even when parameterized by the size of a vertex cover in the superstructure, here we show that a different kind of parameterization—notably by the size of a feedback edge set—yields fixed-parameter tractability. We proceed by showing that this result can be strengthened to a localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph *** then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes fixed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but not least, we show how our results can be extended to the closely related problem of Polytree Learning.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Towards Faster Reasoners by Using Transparent Huge Pages 26th

Towards Faster Reasoners by Using Transparent Huge Pages

引用

26th International Conference on Principles and Practice of Constraint Programming, CP 2020

作者： Fichte, Johannes K. Manthey, Norbert Stecklina, Julian Schidler, André School of Engineering Sciences TU Dresden Dresden Germany Dresden Germany Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030584740

Various state-of-the-art automated reasoning (AR) tools are widely used as backend tools in research of knowledge representation and reasoning as well as in industrial applications. In testing and verification, those tools often run continuously or nightly. In this work, we present an approach to reduce the runtime of AR tools by 10% on average and up to 20% for long running tasks. Our improvement addresses the high memory usage that comes with the data structures used in AR tools, which are based on conflict driven no-good learning. We establish a general way to enable faster memory access by using the memory cache line of modern hardware more effectively. Therefore, we extend the standard C library (glibc) by dynamically allowing to use a memory management feature called huge pages. Huge pages allow to reduce the overhead that is required to translate memory addresses between the virtual memory of the operating system and the physical memory of the hardware. In that way, we can reduce runtime, which in turn decreases costs of running AR tools and applications with similar memory access patterns by linking the tool against this new glibc library when compiling it. In every day industrial applications, runtime savings allow to include more detailed verification tasks, getting better results of any-time optimization algorithms with a bound execution time, and save energy during nightly software builds. To back up the claimed speed-up, we present experimental results for tools that are commonly used in the AR community, including the domains ASP, hardware and software BMC, MaxSAT, and SAT. © 2020, Springer Nature Switzerland AG.

关键词： Cache memory

来源：评论

学校读者我要写书评

暂无评论

An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling

引用

ACM Journal of Experimental Algorithmics 2022年第1期27卷 1-36页

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal Bypass Road Bhauri Madhya Pradesh Bhopal462066 India TU Wien Algorithms and Complexity Group Favoritenstraße 9-11 Vienna1040 Austria

Map labeling is a classical problem in cartography and geographic information systems that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent (i.e., overlap-free) labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each timestep, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sublinear update time. Motivated by this, we study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on fully dynamic (insertion/deletion model) sets of axis-parallel rectangles of two types: (i) uniform height and width and (ii) uniform height and arbitrary width;both settings can be modeled as rectangle intersection graphs. We present the first deterministic algorithm for maintaining an MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with polylogarithmic update time. This breaks the natural barrier of 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 update time. In a subsequent algorithm, we establish the trade-off between approximation quality and update time , for . We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of unit-height and arbitrary-width rectangles with update time, where is the maximum size of an independent set of rectangles stabbed by any horizontal line. We implement our algorithms and report the results of an experimental comparison exploring the trade-off between solution quality and update time for synthetic and real-world map labeling instances. We

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing Hive Plots: A Combinatorial Framework

引用

Journal of Graph algorithms and Applications 2024年第2期28卷 101-129页

作者： Nöllenburg, Martin Wallinger, Markus Algorithms and Complexity Group TU Wien Vienna Austria

Hive plots are a graph visualization style placing vertices on a set of radial axes emanating from a common center and drawing edges as smooth curves connecting their respective endpoints. In previous work on hive plots, assignment to an axis and vertex positions on each axis were determined based on selected vertex attributes and the order of axes was prespecified. Here, we present a new framework focusing on combinatorial aspects of these drawings to extend the original hive plot idea and optimize visual properties such as the total edge length and the number of edge crossings in the resulting hive plots. Our framework comprises three steps: (1) partition the vertices into multiple groups, each corresponding to an axis of the hive plot;(2) optimize the cyclic axis order to bring more strongly connected groups near each other;(3) optimize the vertex ordering on each axis to minimize edge crossings. Each of the three steps is related to a well-studied, but NP-complete computational problem. We combine and adapt suitable exact and heuristic algorithmic approaches, implement them as an instantiation of our framework, and show in a case study how it can be applied in a practical setting. Furthermore, we conduct computational experiments to gain further insights regarding the algorithmic choices of our framework. The code of the implementation and a prototype web application can be found on OSF1. © 2024, Brown University. All rights reserved.

关键词： Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Non-Clashing Teaching Maps for Balls in Graphs 37

Non-Clashing Teaching Maps for Balls in Graphs

引用

37th Annual Conference on Learning Theory, COLT 2024

作者： Chalopin, Jérémie Chepoi, Victor Mc Inerney, Fionn Ratel, Sébastien Aix-Marseille Université Université de Toulon CNRS LIS Marseille France Algorithms and Complexity Group TU Wien Vienna Austria

Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it to be the most efficient machine teaching model satisfying the benchmark for collusion-avoidance set by Goldman and Mathias. A teaching map T for a concept class C assigns a (teaching) set T(C) of examples to each concept C ∈ C. A teaching map is non-clashing if no pair of concepts are consistent with the union of their teaching sets. The size of a non-clashing teaching map (NCTM) T is the maximum size of a teaching set T(C), C ∈ C. The non-clashing teaching dimension NCTD(C) of C is the minimum size of an NCTM for C. NCTM+ and NCTD+(C) are defined analogously, except the teacher may only use positive examples. We study NCTMs and NCTM+s for the concept class B(G) consisting of all balls of a graph G. We show that the associated decision problem B-NCTD+ for NCTD+ is NP-complete in split, co-bipartite, and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails, B-NCTD+ does not admit an algorithm running in time 22o(vc) ·nO(1), nor a kernelization algorithm outputting a kernel with 2o(vc) vertices, where vc is the vertex cover number of G. We complement these lower bounds with matching upper bounds. These are extremely rare results: it is only the second problem in NP to admit such a tight double-exponential lower bound parameterized by vc, and only one of very few problems to admit such an ETH-based conditional lower bound on the number of vertices in a kernel. For trees, interval graphs, cycles, and trees of cycles, we derive NCTM+s or NCTMs for B(G) of size proportional to its VC-dimension. For Gromov-hyperbolic graphs, we design an approximate NCTM+ for B(G) of size 2, in which only pairs of balls with Hausdorff distance larger than some constant must satisfy the non-clashing condition. © 2024 J. Chalopin, V. Chepoi, F. Mc Inerney & S. Ratel.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

MySemCloud: Semantic-aware Word Cloud Editing

MySemCloud: Semantic-aware Word Cloud Editing

引用

Pacific (formerly Asia-Pacific APVIS) Visualization Symposium

作者： Michael Huber Martin Nöllenburg Anaïs Villedieu Algorithms and Complexity Group TU Wien

Word clouds are a popular text visualization technique that summarize an input text by displaying its most important words in a compact image. The traditional layout methods do not take proximity effects between words into account; this has been improved in semantic word clouds, where relative word placement is controlled by edges in a word similarity graph. We introduce MySemCloud, a new human-in-the-loop tool to visualize and edit semantic word clouds. MySemCloud lets users perform computer-assisted local moves of words, which improve or at least retain the semantic quality. To achieve this, we construct a word similarity graph on which a system of forces is applied to generate a compact initial layout with good semantic quality. The force system also allows us to maintain these attributes after each user interaction, as well as preserve the user’s mental map. The tool provides algorithmic support for the editing operations to help the user enhance the semantic quality of the visualization, while adjusting it to their personal preference. We show that MySemCloud provides high user satisfaction as well as permits users to create layouts of higher quality than state-of-the-art semantic word cloud generation tools.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：