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

Fixed-Parameter Tractability of Maximum Colored Path and Beyond

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Fomin, Fedor V. Golovach, Petr A. Korhonen, Tuukka Simonov, Kirill Stamoulis, Giannos Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria LIRMM Université de Montpellier CNRS France

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored n-vertex undirected graph, vertices s and t, and an integer k, finds an (s, t)-path containing at least k different colors in time 2knO(1). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through k specified vertices. It also implies the first 2knO(1) time algorithm for finding an (s, t)-path of length at least k. Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an n-vertex undirected graph G, a matroid M whose elements correspond to the vertices of G and which is represented over a finite field of order q, a positive integer weight function on the vertices of G, two sets of vertices S, T ⊆ V (G), and integers p, k, w, and the task is to find p vertex-disjoint paths from S to T so that the union of the vertices of these paths contains an independent set of M of cardinality k and weight w, while minimizing the sum of the lengths of the paths. We give a 2p+O(k2 log(q+k))nO(1)w time randomized algorithm for this problem. Copyright © 2022, The Authors. All rights reserved.

关键词： Undirected graphs

Balanced Independent and Dominating Sets on Colored Interval Graphs

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bhore, Sujoy Haunert, Jan-Henrik Klute, Fabian Li, Guangping Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Geoinformation Group University of Bonn Bonn Germany Algorithms and Complexity Group TU Wien Vienna Austria

We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely f-Balanced Independent Set (f-BIS) and f-Balanced Dominating Set (f-BDS). Let G = (V, E) be a vertex-colored interval graph with a k-coloring γ : V → {1,..., k} for some k ∈ N. A subset of vertices S ⊆ V is called f-balanced if S contains f vertices from each color class. In the f-BIS and f-BDS problems, the objective is to compute an independent set or a dominating set that is f-balanced. We show that both problems are NP-complete even on proper interval graphs. For the f-BIS problem we design two FPT algorithms, one parameterized by (f, k) for interval graphs and the other parameterized by the vertex cover number for general graphs. Moreover, for the optimization variant of 1-BIS on interval graphs, we show that a simple greedy approach achieves approximation ratio 2. Copyright © 2020, The Authors. All rights reserved.

关键词： Graphic methods

Recognizing Map Graphs of Bounded Treewidth 18

学校读者我要写书评

暂无评论

Recognizing Map Graphs of Bounded Treewidth

18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022

作者： Angelini, Patrizio Bekos, Michael A. Da Lozzo, Giordano Gronemann, Martin Montecchiani, Fabrizio Tappini, Alessandra Department of Mathematics Natural and Applied Sciences John Cabot University Rome Italy Department of Mathematics University of Ioannina Greece Department of Engineering Roma Tre University Rome Italy Algorithms and Complexity Group Technische Universität Wien Austria Department of Engineering University of Perugia Italy

ISBN: (纸本)9783959772365

A map graph is one admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an explicit fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. The algorithm has time complexity that is linear in the size of the graph and, if the input is a yes-instance, it reports a certificate in the form of a so-called witness. Furthermore, this result is developed within a more general algorithmic framework that allows to test, for any k, if the input graph admits a k-map (where at most k nations meet at a common point) or a hole-free k-map (where each point is covered by at least one nation). We point out that, although bounding the treewidth of the input graph also bounds the size of its largest clique, the latter alone does not seem to be a strong enough structural limitation to obtain an efficient time complexity. In fact, while the largest clique in a k-map graph is 3k/2⌉, the recognition of k-map graphs is still open for any fixed k ≥ 5. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Computational complexity

Polynomial-Time Construction of Optimal MPI Derived Datatype Trees

学校读者我要写书评

暂无评论

Polynomial-Time Construction of Optimal MPI Derived Datatype...

International Symposium on Parallel and Distributed Processing (IPDPS)

作者： Robert Ganian Martin Kalany Stefan Szeider Jesper Larsson Träff Algorithms and Complexity Group Vienna University of Technology (TU Wien) Vienna Austria Parallel Computing Group Vienna University of Technology (TU Wien) Vienna Austria

ISBN: (纸本)9781509021413

The derived datatype mechanism is a powerful, integral feature of the Message-Passing Interface (MPI) for communicating arbitrarily structured, possibly non-consecutive and non-homogeneous application data. MPI defines a set of derived datatype constructors of increasing generality, which allows to describe arbitrary data layouts in a reasonably compact fashion. The constructors may be applied recursively, leading to tree-like representations of the application data layouts. Efficient derived datatype representations are required for MPI implementations to efficiently access and process structured application data. We study the problem of finding tree-like representations of MPI derived datatypes that are optimal in terms of space and processing cost. More precisely, we consider the so-called MPI Type Reconstruction Problem of determining a least-cost tree-like representation of a given data layout for a given set of constructors. In an additive cost model that accounts for the space consumption of the constructors and lower-bounds the processing costs, we show that the problem can be solved in polynomial time for the full set of MPI datatype constructors. Our algorithm uses dynamic programming and requires the solution of a series of shortest path problems on an incrementally built, directed, acyclic graph.

关键词： Layout Libraries Indexes complexity theory Data models Heuristic algorithms Dynamic programming

Parameterized study of STEINER TREE on unit disk graphs

学校读者我要写书评

暂无评论

arXiv 2020年

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

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

关键词： Hardness

Worbel: Aggregating Point Labels into Word Clouds

学校读者我要写书评

暂无评论

Worbel: Aggregating Point Labels into Word Clouds

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Technology Bombay Main Gate Rd IIT Area Powai Maharashtra Mumbai400076 India Algorithms and Complexity Group Technische Universität Wien Institute of Logic and Computation Favoritenstraße 9-11 E192-01 Wien1040 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 article, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consist 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 a heuristic with (optional) exact components using SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several synthetic and real-world data sets. Our experiments show that the fully heuristic approach produces solutions of comparable quality to heuristics combined with exact SAT models, while running much faster. © 2023 Copyright held by the owner/author(s).

关键词： Visualization

Non-Clashing Teaching Maps for Balls in Graphs∗

学校读者我要写书评

暂无评论

arXiv 2023年

作者： 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. Copyright © 2023, The Authors. All rights reserved.

关键词： Parameterization

SAMPLE COMPRESSION SCHEMES FOR BALLS IN GRAPHS

学校读者我要写书评

暂无评论

arXiv 2022年

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

One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For a ball B = Br(x) of a graph G = (V,E), a realizable sample for B is a signed subset X = (X+,X−) of V such that B contains X+ and is disjoint from X−. A proper sample compression scheme of size k consists of a compressor and a reconstructor. The compressor maps any realizable sample X to a subsample X′ of size at most k. The reconstructor maps each such subsample X′ to a ball B′ of G such that B′ includes X+ and is disjoint from X−. For balls of arbitrary radius r, we design proper labeled sample compression schemes of size 2 for trees, of size 3 for cycles, of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size 2 for trees and of size 4 for interval graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs. Copyright © 2022, The Authors. All rights reserved.

关键词： Graphic methods

Solving the Steiner Tree Problem with few Terminals

学校读者我要写书评

暂无评论

Solving the Steiner Tree Problem with few Terminals

International Conference on Tools for Artificial Intelligence (ICTAI)

作者： Johannes K. Fichte Markus Hecher André Schidler Institute of Artificial Intelligence TU Dresden Dresden Germany University of Potsdam Germany Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (数字)9781728192284

ISBN: (纸本)9781728185361

The Steiner tree problem is a well-known problem in network design, routing, and VLSI design. Given a graph, edge costs, and a set of dedicated vertices (terminals), the Steiner tree problem asks to output a sub-graph that connects all terminals at minimum cost. A state-of-the-art algorithm to solve the Steiner tree problem by means of dynamic programming is the Dijkstra-Steiner algorithm. The algorithm builds a Steiner tree of the entire instance by systematically searching for smaller instances, based on subsets of the terminals, and combining Steiner trees for these smaller instances. The search heavily relies on a guiding heuristic function in order to prune the search space. However, to ensure correctness, this algorithm allows only for limited heuristic functions, namely, those that satisfy a so-called consistency condition. In this paper, we enhance the Dijkstra-Steiner algorithm and establish a revisited algorithm, called DS*. The DS* algorithm allows for arbitrary lower bounds as heuristics relaxing the previous condition on the heuristic function. Notably, we can now use linear programming based lower bounds. Further, we capture new requirements for a heuristic function in a condition, which we call admissibility. We show that admissibility is indeed weaker than consistency and establish correctness of the DS* algorithm when using an admissible heuristic function. We implement DS* and combine it with modern preprocessing, resulting in an open-source solver (DS*Solve). Finally, we compare its performance on standard benchmarks and observe a competitive behavior.

关键词： Steiner trees Heuristic algorithms Very large scale integration Tools Routing Standards Open source software