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

The Fine-Grained complexity of Graph Homomorphism Parameterized by Clique-Width

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Ganian, Robert Hamm, Thekla Korchemna, Viktoriia Okrasa, Karolina Simonov, Kirill Algorithms and Complexity Group TU Wien Vienna Austria Faculty of Matematics and Information Science Warsaw University of Technology Warsaw Poland Faculty of Mathematics Informatics and Mechanics University of Warsaw Poland

The generic homomorphism problem, which asks whether an input graph G admits a homomorphism into a fixed target graph H, has been widely studied in the literature. In this article, we provide a fine-grained complexity classification of the running time of the homomorphism problem with respect to the clique-width of G (denoted cw) for virtually all choices of H under the Strong Exponential Time Hypothesis. In particular, we identify a property of H called the signature number s(H) and show that for each H, the homomorphism problem can be solved in time O∗(s(H)cw). Crucially, we then show that this algorithm can be used to obtain essentially tight upper bounds. Specifically, we provide a reduction that yields matching lower bounds for each H that is either a projective core or a graph admitting a factorization with additional properties—allowing us to cover all possible target graphs under long-standing *** Codes 68R10 © 2022, CC BY.

关键词：

Planarizing Graphs and their Drawings by Vertex Splitting

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Nöllenburg, Martin Sorge, Manuel Terziadis, Soeren Villedieu, Anaïs Wu, Hsiang-Yun Wulms, Jules Algorithms and Complexity Group Tu Wien Vienna Austria Research Unit of Computer Graphics Tu Wien Vienna Austria St. Pölten University of Applied Sciences Austria

The splitting number of a graph G = (V, E) is the minimum number of vertex splits required to turn G into a planar graph, where a vertex split removes a vertex v ∈ V, introduces two new vertices v1, v2, and distributes the edges formerly incident to v among v1, v2. The splitting number problem is known to be NP-complete for abstract graphs and we provide a non-uniform fixed-parameter tractable (FPT) algorithm for this problem. We then shift focus to the splitting number of a given topological graph drawing in R2, where the new vertices resulting from vertex splits must be re-embedded into the existing drawing of the remaining graph. We show NP-completeness of this embedded splitting number problem, even for its two subproblems of (1) selecting a minimum subset of vertices to split and (2) for re-embedding a minimum number of copies of a given set of vertices. For the latter problem we present an FPT algorithm parameterized by the number of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition. © 2022, CC BY.

关键词： Drawing (graphics)

On strict (Outer-)confluent graphs

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2021年第1期25卷 481-512页

作者： Förster, Henry Ganian, Robert Klute, Fabian Nöllenburg, Martin University of Tübingen Tübingen Germany Algorithms and Complexity Group TU Wien Vienna Austria Utrecht University Utrecht Netherlands

A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by unique smooth paths through a planar system of junctions and arcs. If all vertices of the graph lie in the outer face of the drawing, the drawing is called a strict outerconfluent (SOC) drawing. SC and SOC graphs were first considered by Eppstein et al. in Graph Drawing 2013. Here, we establish several new relationships between the class of SC graphs and other graph classes, in particular string graphs and unit-interval graphs. Further, we extend earlier results about special bipartite graph classes to the notion of strict outerconfluency, show that SOC graphs have cop number two, and establish that tree-like (∆-)SOC graphs have bounded cliquewidth. © 2021, Brown University. All rights reserved.

关键词： Trees (mathematics)

Exact algorithms for Clustered Planarity with Linear Saturators

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Da Lozzo, Giordano Ganian, Robert Gupta, Siddharth Mohar, Bojan Ordyniak, Sebastian Zehavi, Meirav Roma Tre University Italy Algorithms and Complexity Group TU Wien Vienna Austria BITS Pilani K K Birla Goa Campus India Department of Mathematics Simon Fraser University BurnabyBC Canada University of Leeds United Kingdom Ben-Gurion University of the Negev Beer-Sheva Israel

We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an n-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths—one for each cluster—that connect all the vertices in each cluster while maintaining planarity. We show that the problem can be solved in time 2O(n) for both the variable and fixed embedding case. Moreover, we show that it can be solved in subexponential time 2O(√n log n) in the fixed embedding case if additionally the input graph is connected. The latter time complexity is tight under the Exponential-Time Hypothesis. We also show that n can be replaced with the vertex cover number of the input graph by providing a linear (resp. polynomial) kernel for the variable-embedding (resp. fixed-embedding) case;these results contrast the NP-hardness of the problem on graphs of bounded treewidth (and even on trees). Finally, we complement known lower bounds for the problem by showing that Clustered Planarity with Linear Saturators is NP-hard even when the number of clusters is at most 3, thus excluding the algorithmic use of the number of clusters as a parameter. © 2024, CC BY.

关键词： Graph embeddings

Drawing Shortest Paths in Geodetic Graphs

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2022年第3期26卷 353-361页

作者： Cornelsen, Sabine Pfister, Maximilian Förster, Henry Gronemann, Martin Hoffmann, Michael Kobourov, Stephen Schneck, Thomas University of Konstanz Germany University of Tübingen Germany Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer Science ETH Zürich Switzerland Department of Computer Science University of Arizona United States

Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph G, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of G, i.e., a drawing of G in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing. On the positive side we show that geodetic graphs admit a philogeodetic drawing if both the diameter and the density are very low. © 2022, Brown University. All rights reserved.

关键词： Graphic methods

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

Worbel: Aggregating point labels into word clouds

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Vienna Austria

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster. © 2021, CC BY.

关键词： Visualization

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

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bartier, Valentin Defrain, Oscar Inerney, Fionn Mc Univ Lyon CNRS INSA Lyon UCBL Centrale Lyon Univ Lyon 2 LIRIS UMR5205 VilleurbanneF-69622 France Aix-Marseille Université CNRS LIS Marseille13009 France Algorithms and Complexity Group TU Wien Austria

At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an nO(d)-delay algorithm listing all minimal transversals of an n-vertex hyqpergraph of degeneracy d. Recently at IWOCA 2019, Conte, Kanté, Marino, and Uno asked whether this XP-delay algorithm parameterized by d could be made FPT-delay for a weaker notion of degeneracy, or even parameterized by the maximum degree ∆, i.e., whether it can be turned into an algorithm with delay f(∆) · nO(1) for some computable function f. Moreover, and as a first step toward answering that question, they note that they could not achieve these time bounds even for the particular case of minimal dominating sets enumeration. In this paper, using ordered generation, we show that an FPT-delay algorithm can be devised for minimal transversals enumeration parameterized by the degeneracy and dimension, giving a positive and more general answer to the latter question. © 2023, CC BY.

关键词： Parameter estimation