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

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

来源：评论

学校读者我要写书评

暂无评论

Counting Vanishing Matrix-Vector Products

arXiv

引用

arXiv 2023年

作者： Brand, Cornelius Korchemna, Viktoriia Skotnica, Michael Simonov, Kirill Algorithms and Complexity Group TU Wien Austria Department of Applied Mathematics Charles University Prague Czech Republic Hasso Plattner Institute University of Potsdam Germany

Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let v ∈ Qd be a rational vector, (T1, T2 . . . Tm) a list of d × d rational matrices, S ∈ Qh×d a rational matrix not necessarily square and k a parameter. The goal is to compute the number of ways one can choose k matrices Ti1 , Ti2 , . . ., Tik from the list such that STik · · · Ti1 v = 0 ∈ Qh. In this paper, we show that this problem is #W[2]-hard for parameter k. As a consequence, computing the k-th homotopy group of a d-dimensional 1-connected topological space for d > 3 is #W[2]-hard for parameter k. We also discuss a decision version of the problem and its several modifications for which we show W[1]/W[2]-hardness. This is in contrast to the parameterized k-sum problem, which is only W[1]-hard (Abboud-Lewi-Williams, ESA’14). In addition, we show that the decision version of the problem without parameter is an undecidable problem, and we give a fixed-parameter tractable algorithm for matrices of bounded size over finite fields, parameterized the matrix dimensions and the order of the field. Copyright © 2023, The Authors. All rights reserved.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

A Dynamic MaxSAT-based Approach to Directed Feedback Vertex Sets

arXiv

引用

arXiv 2022年

作者： Kiesel, Rafael Schidler, André Institute of Logic and Computation Tu Wien Vienna Austria Algorithms and Complexity Group Tu Wien Vienna Austria

We propose a new approach to the Directed Feedback Vertex Set Problem (DFVSP), where the input is a directed graph and the solution is a minimum set of vertices whose removal makes the graph acyclic. Our approach, implemented in the solver DAGer, is based on two novel contributions: Firstly, we add a wide range of data reductions that are partially inspired by reductions for the similar vertex cover problem. For this, we give a theoretical basis for lifting reductions from vertex cover to DFVSP but also incorporate novel ideas into strictly more general and new DFVSP reductions. Secondly, we propose dynamically encoding DFVSP in propositional logic using cycle propagation for improved performance. Cycle propagation builds on the idea that already a limited number of the constraints in a propositional encoding is usually sufficient for finding an optimal solution. Our algorithm, therefore, starts with a small number of constraints and cycle propagation adds additional constraints when necessary. We propose an efficient integration of cycle propagation into the workflow of MaxSAT solvers, further improving the performance of our algorithm. Our extensive experimental evaluation shows that DAGer significantly outperforms the state-of-the-art solvers and that our data reductions alone directly solve many of the instances. Copyright © 2022, The Authors. All rights reserved.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

complexity of Deciding Injectivity and Surjectivity of ReLU Neural Networks

arXiv

引用

arXiv 2024年

作者： Froese, Vincent Grillo, Moritz Skutella, Martin Technische Universität Berlin Faculty IV Institute of Software Engineering and Theoretical Computer Science Algorithmics and Computational Complexity Germany Technische Universität Berlin Faculty II Institute of Mathematics Combinatorial Optimization and Graph Algorithms Germany

Neural networks with ReLU activation play a key role in modern machine learning. In view of safety-critical applications, the verification of trained networks is of great importance and necessitates a thorough understanding of essential properties of the function computed by a ReLU network, including characteristics like injectivity and surjectivity. Recently, Puthawala et al. [JMLR 2022] came up with a characterization for injectivity of a ReLU layer, which implies an exponential-time algorithm. However, the exact computational complexity of deciding injectivity remained open. We answer this question by proving coNP-completeness of deciding injectivity of a ReLU layer. On the positive side, as our main result, we present a parameterized algorithm which yields fixed-parameter tractability of the problem with respect to the input dimension. In addition, we also characterize surjectivity for two-layer ReLU networks with one-dimensional output. Remarkably, the decision problem turns out to be the complement of a basic network verification task. We prove NP-hardness for surjectivity, implying a stronger hardness result than previously known for the network verification problem. Finally, we reveal interesting connections to computational convexity by formulating the surjectivity problem as a zonotope containment problem. © 2024, CC BY.

关键词： Complex networks

来源：评论

学校读者我要写书评

暂无评论

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

arXiv

引用

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

来源：评论

学校读者我要写书评

暂无评论

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)

来源：评论

学校读者我要写书评

暂无评论

Graph drawing applications in combinatorial theory of maturity models

arXiv

引用

arXiv 2024年

作者： Kajzer, Špela Dobler, Alexander Jerebic, Janja Nöllenburg, Martin Orthaber, Joachim Bokal, Drago Faculty of Natural Sciences and Mathematics University of Maribor Slovenia Institute of Mathematics Physics and Mechanics Ljubljana Slovenia Algorithms and Complexity Group TU Wien Austria Faculty of Organizational Sciences University of Maribor Slovenia Institute of Software Technology Graz University of Technology Austria

In this paper, we introduce tiled graphs as models of learning and maturing processes. We show how tiled graphs can combine graphs of learning spaces or antimatroids (partial hypercubes) and maturity models (total orders) to yield models of learning processes. For the visualization of these processes it is a natural approach to aim for certain optimal drawings. We show for most of the more detailed models that the drawing problems resulting from them are NP-complete. The terse model of a maturing process that ignores the details of learning, however, results in a polynomially solvable graph drawing problem. In addition, this model provides insight into the process by ordering the subjects at each test of their maturity. We investigate extremal and random instances of this problem, and provide exact results and bounds on their optimal crossing number. Graph-theoretic models offer two approaches to the design of optimal maturity models given observed data: (1) minimizing intra-subject inconsistencies, which manifest as regressions of subjects, is modeled as the well-known feedback arc set problem. We study the alternative of (2) finding a maturity model by minimizing the inter-subject inconsistencies, which manifest as crossings in the respective drawing. We show this to be NP-complete. © 2024, CC BY.

关键词： Optimization

来源：评论

学校读者我要写书评

暂无评论

Space-Efficient Parameterized algorithms on Graphs of Low Shrubdepth

arXiv

引用

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

来源：评论

学校读者我要写书评

暂无评论

A Survey on Graph Problems Parameterized Above and Below Guaranteed Values

arXiv

引用

arXiv 2022年

作者： Gutin, Gregory Mnich, Matthias Royal Holloway University of London Department of Computer Science Egham United Kingdom Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values. Those problems seek, for a given graph G, a solution whose value is at least g(G) + k or at most g(G) − k, where g(G) is a guarantee on the value that any solution on G takes. The goal is to design algorithms which find such solution in time whose complexity in k is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems. Copyright © 2022, The Authors. All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Untangling Circular Drawings: algorithms and complexity 32

Untangling Circular Drawings: Algorithms and Complexity

引用

32nd International Symposium on algorithms and Computation, ISAAC 2021

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Austria Universität Passau Germany Research Unit of Computer Graphics TU Wien Austria

ISBN: (纸本)9783959772143

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G = (V, E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift◦(δG) as the minimum number of vertices that need to be shifted to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift◦(δG) ≤ K for a given integer K, is NP-complete. Based on this result we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case we provide a tight upper bound shift◦(δG) ≤ ⌊n2 ⌋ - 1, where n is the number of vertices in G, and present a polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. © Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：