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

arXiv 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 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

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. © 2022, CC BY.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Finding a battleship of uncertain shape

arXiv

引用

arXiv 2022年

作者： Hainzl, Eva-Maria Löffler, Maarten Perz, Daniel Tkadlec, Josef Wallinger, Markus Institute of Discrete Mathematics and Geometry TU Wien Austria Department of Computing and Information Sciences Utrecht University Netherlands Institute of Software Technology TU Graz Austria Department of Mathematics Harvard University United States Algorithms and Complexity Group TU Wien Austria

Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension d ϵ {1, 2}. A ship is a subset of d. Given a family F of ships, we say that an infinite subset X ⊂ dof the cells pierces F, if it intersects each translate of each ship in F (by a vector in d). In this work, we study the lowest possible (asymptotic) density π(F) of such a piercing subset. To our knowledge, this problem has previously been studied only in the special case |F| = 1 (a single ship). As our main contribution, we present a formula for π(F) when F consists of 2 ships of size 2 each, and we identify the toughest families in several other cases. We also implement an algorithm for finding π(F) in 1D. © 2022, CC BY.

关键词： Ships

来源：评论

学校读者我要写书评

暂无评论

Recognizing DAGs with Page-Number 2 is NP-complete

arXiv

引用

arXiv 2022年

作者： Bekos, Michael A. Da Lozzo, Giordano Frati, Fabrizio Gronemann, Martin McHedlidze, Tamara Raftopoulou, Chrysanthi Department of Mathematics University of Ioannina Ioannina Greece Department of Engineering Roma Tre University Italy Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer Science Utrecht University Utrecht Netherlands School of Applied Mathematical & Physical Sciences NTUA Athens Greece

The page-number of a directed acyclic graph (a DAG, for short) is the minimum k for which the DAG has a topological order and a k-coloring of its edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured that the recognition of DAGs with page-number 2 is NP-complete and proved that recognizing DAGs with page-number 6 is NP-complete [SIAM J. Computing, 1999]. Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number k is NP-complete, for every k ≥ 3 [SoCG 2019]. In this paper, we finally resolve Heath and Pemmaraju's conjecture in the affirmative. In particular, our NP-completeness result holds even for st-planar graphs and planar posets. Copyright © 2022, The Authors. All rights reserved.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for book embedding problems

引用

Journal of Graph algorithms and Applications 2020年第4期24卷 603-620页

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria Engineering Department University of Perugia Perugia Italy

A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether G admits a k-page book embedding both when the linear order of the vertices is fixed, called Fixed-Order Book Thick-ness, or not fixed, called Book Thickness. Both problems are known to be NP-complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order. © 2020, Brown University. All rights reserved.

关键词： Embeddings

来源：评论

学校读者我要写书评

暂无评论

On Turn-Regular Orthogonal Representations

引用

Journal of Graph algorithms and Applications 2022年第3期26卷 285-296页

作者： Bekos, Michael A. Binucci, Carla Di Battista, Giuseppe Didimo, Walter Gronemann, Martin Klein, Karsten Patrignani, Maurizio Rutter, Ignaz Department of Mathematics University of Ioannina Ioannina Greece Department of Engineering University of Perugia Perugia Italy Department of Engineering Roma Tre University Italy Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer and Information Science University of Konstanz Konstanz Germany Department of Computer Science and Mathematics University of Passau Germany

An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other" inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast, finding a minimum-area drawing of H is NP-hard if H is non-turn-regular. This scenario naturally motivates the study of which graphs admit turn-regular orthogonal representations. In this paper we identify notable classes of biconnected planar graphs that always admit such repre-sentations, which can be computed in linear time. We also describe a linear-time testing algorithm for trees and provide a polynomial-time algorithm that tests whether a bi-connected plane graph with "small" faces has a turn-regular orthogonal representation without bends. © 2022, Brown University. All rights reserved.

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Recognizing Map Graphs of Bounded Treewidth

arXiv

引用

arXiv 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 Ioannina Greece Department of Engineering Roma Tre University Rome Italy Algorithms and Complexity Group TU Wien Vienna Austria Department of Engineering University of Perugia Perugia Italy

A map graph is a graph 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 of the sphere 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 b3k/2c, the recognition of k-map graphs is still open for any fixed k ≥ 5. Copyright © 2022, The Authors. All rights reserved.

关键词： Machine learning

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the upward book thickness problem: Combinatorial and complexity results

arXiv

引用

arXiv 2021年

作者： Bhore, Sujoy da Lozzo, Giordano Montecchiani, Fabrizio Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Roma Tre University Rome Italy Department of Engineering University of Perugia Italy Algorithms and Complexity Group TU Wien Vienna Austria

A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are st-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP-hard for any fixed k ≥ 3. We show that the problem, for any k ≥ 5, remains NP-hard for graphs whose domination number is O(k), but it is FPT in the vertex cover number. © 2021, CC BY.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Resolving Infeasibility of Linear Systems: A Parameterized Approach

arXiv

引用

arXiv 2022年

作者： Bérczi, Kristóf Göke, Alexander Mendoza-Cadena, Lydia Mirabel Mnich, Matthias MTA-ELTE Momentum Matroid Optimization Research Group MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany MTA-ELTE Momentum Matroid Optimization Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary

Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to data inaccuracies or modeling errors, in practical applications one often faces linear systems that are infeasible. Extensive theoretical and practical methods have been proposed for post-infeasibility analysis of linear systems. This generally amounts to detecting a feasibility blocker of small size k, which is a set of equations and inequalities whose removal or perturbation from the large system of size m yields a feasible system. This motivates a parameterized approach towards post-infeasibility analysis, where we aim to find a feasibility blocker of size at most k in fixed-parameter time f(k) · mO(1). We establish parameterized intractability (W[1]- and NP-hardness) results already in very restricted settings for different choices of the parameters maximum size of a deletion set, number of positive/negative right-hand sides, treewidth, pathwidth and treedepth. Additionally, we rule out a polynomial compression for MinFB parameterized by the size of a deletion set and the number of negative right-hand sides. Furthermore, we develop fixed-parameter algorithms parameterized by various combinations of these parameters when every row of the system corresponds to a difference constraint. Our algorithms capture the case of Directed Feedback Arc Set, a fundamental parameterized problem whose fixed-parameter tractability was shown by Chen et al. (STOC 2008). Copyright © 2022, The Authors. All rights reserved.

关键词： Linear systems

来源：评论

学校读者我要写书评

暂无评论

Single-Peaked Opinion Updates

arXiv

引用

arXiv 2022年

作者： Bredereck, Robert George, Anne-Marie Israel, Jonas Kellerhals, Leon Algorithm Engineering Humboldt-Universität Berlin Germany Institut für Informatik TU Clausthal Germany Analytical Solutions and Reasoning University of Oslo Germany Research Group Efficient Algorithms Technische Universität Berlin Germany Algorithmics and Computational Complexity Technische Universität Berlin Germany

We consider opinion diffusion for undirected networks with sequential updates when the opinions of the agents are single-peaked preference rankings. Our starting point is the study of preserving single-peakedness. We identify voting rules that, when given a single-peaked profile, output at least one ranking that is single peaked w.r.t. a single-peaked axis of the input. For such voting rules we show convergence to a stable state of the diffusion process that uses the voting rule as the agents’ update rule. Further, we establish an efficient algorithm that maximises the spread of extreme opinions. Copyright © 2022, The Authors. All rights reserved.

关键词： Machine learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：