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

Space-Efficient Parameterized algorithms on Graphs of Low Shrubdepth

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bergougnoux, Benjamin Chekan, Vera Ganian, Robert Kanté, Mamadou Moustapha Mnich, Matthias Oum, Sang-Il Pilipczuk, Michal van Leeuwen, Erik Jan Institute of Informatics University of Warsaw Poland Humboldt-Universität zu Berlin Germany Algorithms and Complexity Group TU Wien Vienna Austria Université Clermont Auvergne Clermont Auvergne INP LIMOS CNRS Clermont-Ferrand France Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Daejeon Korea Republic of Department of Mathematical Sciences KAIST Daejeon Korea Republic of Dept. Information and Computing Sciences Utrecht University Netherlands

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, Independent Set can be solved in time 2O(dk) · nO(1) using O(dk2 log n) space;Max Cut can be solved in time nO(dk) using O(dk log n) space;and Dominating Set can be solved in time 2O(dk) · nO(1) using nO(1) space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial. Copyright © 2023, The Authors. All rights reserved.

关键词： Dynamic programming

Geometric Planar Networks on Bichromatic Collinear Points

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bandyapadhyay, Sayan Banik, Aritra Bhore, Sujoy Nöllenburg, Martin Department of Informatics University of Bergen Norway School of Computer Sciences NISER Bhubaneswar India Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group Technische Universität Wien Austria

We study three classical graph problems – Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems for collinear points. We show that almost all of these problems can be solved in linear time in this setting. © 2019, CC BY.

关键词： Hamiltonians

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Galby, Esther Munaro, Andrea Yang, Shizhou Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Department of Mathematical Physical and Computer Sciences University of Parma Parma Italy School of Mathematics and Physics Queen's University Belfast Belfast United Kingdom

We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth. Copyright © 2023, The Authors. All rights reserved.

关键词： Polynomial approximation

Deterministic random walks on regular trees 08

学校读者我要写书评

暂无评论

Deterministic random walks on regular trees

Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

作者： Joshua Cooper Benjamin Doerr Tobias Friedrich Joel Spencer University of South Carolina Columbia SC Algorithms and Complexity Max-Planck-Institut für Informatik Saarbrücken Germany Courant Institute of Mathematical Sciences New York University New York NY

Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed *** and Spencer (Comb. Probab. Comput. (2006)) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid Zd and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips deviates from the expected number the random walk would have gotten there, by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its *** result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite k-ary tree (k ≥ 3), we show that for any deviation D there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least D more chips than expected in the random walk model. However, to achieve a deviation of D it is necessary that at least kΘ(D) vertices contribute by being occupied by a number of chips not divisible by k in a certain time interval.

关键词：

Longest Cycle above Erdos–Gallai Bound

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill Sagunov, Danil 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

In 1959, Erdos and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2O(k) · nO(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G) + k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own. © 2022, CC BY.

关键词： Graph theory

Symmetry properties of generalized graph truncations

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Eiben, Eduard Jajcay, Robert Šparl, Primož Algorithms and Complexity Group TU Wien Vienna Austria Comenius University Bratislava Slovakia University of Primorska Institute Andrej Marušič Koper Slovenia University of Ljubljana Faculty of Education Ljubljana Slovenia Institute of Mathematics Physics and Mechanics Ljubljana Slovenia

In the generalized truncation construction, one replaces each vertex of a k-regular graph Γ with a copy of a graph Υ of order k. We investigate the symmetry properties of the graphs constructed in this way, especially in connection to the symmetry properties of the graphs Γ and Υ used in the construction. We demonstrate the usefulness of our results by using them to obtain a classification of cubic vertex-transitive graphs of girths 3, 4, and *** Codes 05C25, 05C38 Copyright © 2017, The Authors. All rights reserved.

关键词：

Tight complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Focke, Jacob Marx, Dániel Inerney, Fionn Mc Neuen, Daniel Sankar, Govind S. Schepper, Philipp Wellnitz, Philip CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria School of Computing Science Simon Fraser University Canada Duke University United States Max Planck Institute for Informatics SIC Germany

For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u) ∩ S| ∈ σ for every u ∈ S, and |N(v) ∩ S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies common problems like Independent Set, Dominating Set, Independent Dominating Set, and many others. In an accompanying paper, it is proven that, for all pairs of finite or cofinite sets (σ, ρ), there is an algorithm that counts (σ, ρ)-sets in time (cσ,ρ)tw · nO(1) (if a tree decomposition of width tw is given in the input). Here, cσ,ρ is a constant with an intricate dependency on σ and ρ. Despite this intricacy, we show that the algorithms in the accompanying paper are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any Ε > 0, a (cσ,ρ − Ε)tw · nO(1)-algorithm counting the number of (σ, ρ)-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that those algorithms are optimal in this setting as well. Copyright © 2023, The Authors. All rights reserved.

关键词： Trees (mathematics)

Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yang, Shizhou Galby, Esther Munaro, Andrea Department of Mathematical Physical and Computer Sciences University of Parma Parma Italy School of Mathematics and Physics Queen’s University Belfast Belfast United Kingdom Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

We investigate a relaxation of the notion of fractional treewidth-fragility, namely fractional tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for meta-problems such as finding a maximum-weight sparse induced subgraph satisfying a given CMSO2 formula on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth, and its applications to exact subexponential-time *** Codes 05C85, 05C75, 05C62, 68W25 Copyright © 2024, The Authors. All rights reserved.

关键词： Polynomial approximation

Approximation algorithms for coupled task scheduling minimizing the sum of completion times

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Fischer, David Györgyi, Péter Institute of Algorithms and Complexity Hamburg University of Technology Blohmstraße 15 Hamburg21079 Germany Institute for Computer Science and Control Eötvös Loránd Research Network Kende Str. 13-17. Budapest1111 Hungary

In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be NP-hard, while also proving NP-hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task *** Codes 90B35 © 2022, CC BY.

关键词： Approximation algorithms