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

Detours in Directed Graphs 39

学校读者我要写书评

暂无评论

Detours in Directed Graphs

39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022

作者： Fomin, Fedor V. Golovach, Petr A. Lochet, William Sagunov, Danil Simonov, Kirill Saurabh, Saket Department of Informatics University of Bergen Norway St. Petersburg Department of V.A. Steklov Institute of Mathematics Russia JetBrains Research Saint Petersburg Russia Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences HBNI Chennai India

ISBN: (纸本)9783959772228

We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s, t)-path of length at least distG(s, t) + k (where distG(s, t) denotes the length of a shortest path from s to t). Bezáková et al. [7] proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2O(k) · n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2O(k) · nO(1) time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G) + k (diam(G) denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path above Diameter is NP-complete even for k = 1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path above Diameter is solvable in polynomial time for each k ∈ {1, . . ., 4} and is NP-complete for every k ≥ 5. The parameterized complexity of Longest Detour on general directed graphs remains an interesting open problem. © Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh.

关键词： Directed graphs

Polynomial kernels for edge modification problems towards block and strictly chordal graphs

学校读者我要写书评

暂无评论

Discrete Mathematics and Theoretical Computer Science 2025年 272卷

作者： Dumas, Maël Perez, Anthony Rocton, Mathis Todinca, Ioan Institute of Informatics University of Warsaw Warsaw Poland Université d’Orléans INSA CVL LIFO UR 4022 Orléans France Algorithms and Complexity Group TU Wien Vienna Austria

We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph G = (V, E) and an integer k ∈ N and seeks to edit (add or delete) at most k edges from G to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide: © 2025 by the author(s)

关键词： Graphic methods

Unit Disk Representations of Embedded Trees, Outerplanar and Multi-legged Graphs 29th

学校读者我要写书评

暂无评论

Unit Disk Representations of Embedded Trees, Outerplanar an...

29th International Symposium on Graph Drawing and Network Visualization, GD 2021

作者： Bhore, Sujoy Löffler, Maarten Nickel, Soeren Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Department of Computing and Information Sciences Utrecht University Utrecht Netherlands Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030929305

A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-disjoint disks is called a unit disk contact representation (UDC). We prove that it is NP -hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that it can be decided in linear time if a lobster graph admits a weak UDC, which permits intersections between disks of non-adjacent vertices. © 2021, Springer Nature Switzerland AG.

关键词： Trees (mathematics)

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

On the fine-grained parameterized complexity of partial scheduling to minimize the makespan 15

学校读者我要写书评

暂无评论

On the fine-grained parameterized complexity of partial sche...

15th International Symposium on Parameterized and Exact Computation, IPEC 2020

作者： Nederlof, Jesper Swennenhuis, Céline M.F. Utrecht University Algorithms and Complexity Group Netherlands Eindhoven University of Technology Combinatorial Optimization Group Netherlands

ISBN: (纸本)9783959771726

We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f(k)nO(1) or nO(f(k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in P, NP-complete and fixed-parameter tractable by k, or W[1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an O(8kk(|V | + |E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V, E) is the graph with precedence constraints. © Jesper Nederlof and Céline M. F. Swennenhuis

关键词： Parameterization

A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots

学校读者我要写书评

暂无评论

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

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

The Parameterized complexity of Coordinated Motion Planning

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad 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

In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target—prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n2 − 1)-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish—as a simpler case—the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids. © 2023, CC BY.

关键词： Robots

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