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

Counting Vanishing Matrix-Vector Products

学校读者我要写书评

暂无评论

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

Balanced connected subgraph problem in geometric intersection graphs

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bhore, Sujoy Jana, Satyabrata Pandit, Supantha Roy, Sasanka Algorithms and Complexity Group TU Wien Vienna Austria Indian Statistical Institute Kolkata India Dhirubhai Ambani Institute of Information and Communication Technology Gandhinagar Gujarat India

We study the Balanced Connected Subgraph (shortly, BCS) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given a vertex-colored graph G = (V, E), where each vertex in V is colored with either "red" or "blue", the BCS problem seeks a maximum cardinality induced connected subgraph H of G such that H is color-balanced, i.e., H contains an equal number of red and blue vertices. We study the computational complexity landscape of the BCS problem while considering geometric intersection graphs. On one hand, we prove that the BCS problem is NP-hard on the unit disk, outer-string, complete grid, and unit square graphs. On the other hand, we design polynomial-time algorithms for the BCS problem on interval, circular-arc and permutation graphs. In particular, we give algorithm for the Steiner Tree problem on both the interval graphs and circular arc graphs, that is used as a subroutine for solving BCS problem on same graph classes. Finally, we present a FPT algorithm for the BCS problem on general graphs. Copyright © 2019, The Authors. All rights reserved.

关键词： Trees (mathematics)

The Computational complexity of Concise Hypersphere Classification

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Royal Holloway University of London United Kingdom Algorithms and Complexity Group TU Wien Austria DePaul University United States University of Leeds United Kingdom

Hypersphere classification is a classical and foundational method that can provide easy-to-process explanations for the classification of real-valued and binary data. However, obtaining an (ideally concise) explanation via hypersphere classification is much more difficult when dealing with binary data than real-valued data. In this paper, we perform the first complexity-theoretic study of the hypersphere classification problem for binary data. We use the fine-grained parameterized complexity paradigm to analyze the impact of structural properties that may be present in the input data as well as potential conciseness constraints. Our results include stronger lower bounds and new fixed-parameter algorithms for hypersphere classification of binary data, which can find an exact and concise explanation when one exists. © 2023, CC BY.

关键词： Classification (of information)

Partitioning graph drawings and triangulated simple polygons into greedily routable regions

学校读者我要写书评

暂无评论

International Journal of Computational Geometry and Applications 2017年第1-2期27卷 121-158页

作者： Nöllenburg, Martin Prutkin, Roman Rutter, Ignaz Algorithms and Complexity Group TU Wien Vienna Austria Institute of Theoretical Informatics Karlsruhe Institute of Technology Karlsruhe Germany Algorithms and Visualization WandI Technische Universiteit Eindhoven Eindhoven Netherlands

A greedily routable region (GRR) is a closed subset of ℝ2, in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected. © 2017 World Scientific Publishing Company.

关键词： Decomposing graph drawings Greedy region decomposition Greedy routing in wireless sensor networks Increasing-chord drawings

Algorithmic Extensions of Dirac's Theorem

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill Department of Informatics University of Bergen Norway St. Petersburg Department V.A. Steklov Institute of Mathematics Russia Algorithms and Complexity Group TU Wien Austria

In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every n-vertex 2-connected graph G with minimum vertex degree δ ≥ 2 contains a cycle with at least min{2δ, n} vertices. In particular, if δ ≥ n/2, then G is Hamiltonian. The proof of Dirac's theorem is constructive, and it yields an algorithm computing the corresponding cycle in polynomial time. The combinatorial bound of Dirac's theorem is tight in the following sense. There are 2-connected graphs that do not contain cycles of length more than 2δ + 1. Also, there are non-Hamiltonian graphs with all vertices but one of degree at least n/2. This prompts naturally to the following algorithmic questions. For k ≥ 1, (A) How difficult is to decide whether a 2-connected graph contains a cycle of length at least min{2δ + k, n}? (B) How difficult is to decide whether a graph G is Hamiltonian, when at least n - k vertices of G are of degrees at least n/2 - k? The first question was asked by Fomin, Golovach, Lokshtanov, Panolan, Saurabh, and Zehavi. The second question is due to Jansen, Kozma, and Nederlof. Even for a very special case of k = 1, the existence of a polynomial-time algorithm deciding whether G contains a cycle of length at least min{2δ + 1, n} was open. We resolve both questions by proving the following algorithmic generalization of Dirac's theorem: If all but k vertices of a 2-connected graph G are of degree at least δ, then deciding whether G has a cycle of length at least min{2δ + k, n} can be done in time 2O(k) nO(1). The proof of the algorithmic generalization of Dirac's theorem builds on new graph-theoretical results that are interesting on their own. Copyright © 2020, The Authors. All rights reserved.

关键词： Hamiltonians

Bounding and Computing Obstacle Numbers of Graphs 30

学校读者我要写书评

暂无评论

Bounding and Computing Obstacle Numbers of Graphs

30th Annual European Symposium on algorithms, ESA 2022

作者： Balko, Martin Chaplick, Steven Ganian, Robert Gupta, Siddharth Hoffmann, Michael Valtr, Pavel Wolff, Alexander Faculty of Mathematics and Physics Charles University Prague Czech Republic Maastricht University Netherlands Algorithms and Complexity Group TU Wien Austria Department of Computer Science University of Warwick Coventry United Kingdom Department of Computer Science ETH Zürich Switzerland Institut für Informatik Universität Würzburg Germany

ISBN: (纸本)9783959772471

An obstacle representation of a graph G consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each n-vertex graph is O(n log n) [Balko, Cibulka, and Valtr, 2018] and that there are n-vertex graphs whose obstacle number is Ω(n/(log log n)2) [Dujmovic and Morin, 2015]. We improve this lower bound to Ω(n/ log log n) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmovic and Morin. We also show that if the drawing of some n-vertex graph is given as part of the input, then for some drawings Ω(n2) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed-parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP-hard to decide whether G admits an obstacle representation using P as the only obstacle. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Graph theory

Ca-Re-Chord: A Churn Resistant Self-Stabilizing Chord Overlay Network

学校读者我要写书评

暂无评论

Ca-Re-Chord: A Churn Resistant Self-Stabilizing Chord Overla...

International Conference and Workshops on Networked Systems (NetSys)

作者： Markus Benter Mohammad Divband Sebastian Kniesburges Andreas Koutsopoulos Kalman Graffi Algorithms and Complexity Group University of Paderborn Germany Universitat Paderborn Paderborn Nordrhein-Westfalen DE Theory of Distributed Systems Group University of Paderborn Germany Technology of Social Networks Group University of Düsseldorf Germany

Self-stabilization is the property of a system to transfer itself regardless of the initial state into a legitimate state. Chord as a simple, decentralized and scalable distributed hash table is an ideal showcase to introduce self-stabilization for p2p overlays. In this paper, we present Re-Chord, a self-stabilizing version of Chord. We show, that the stabilization process is functional, but prone to strong churn. For that, we present Ca-Re-Chord, a churn resistant version of Re-Chord, that allows the creation of a useful DHT in any kind of graph regardless of the initial state. Simulation results attest the churn resistance and good performance of Ca-Re-Chord.

关键词： Peer-to-peer computing Resistance Routing Robustness Overlay networks Social network services Educational institutions

Level Planarity Is More Difficult Than We Thought

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Fink, Simon D. Pfretzschner, Matthias Rutter, Ignaz Stumpf, Peter Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Computer Science and Mathematics University of Passau Germany Charles University Prague Czech Republic

We consider three simple quadratic time algorithms for the problem Level Planarity and give a level-planar instance that they either falsely report as negative or for which they output a drawing that is not level plan... 详细信息

关键词： Consensus algorithm

Parameterized complexity and approximability of directed odd cycle transversal

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Lokshtanov, Daniel Ramanujan, M.S. Saurabh, Saket Zehavi, Meirav University of Bergen Bergen Norway Algorithms and Complexity Group TU Wien Vienna Austria Institute of Mathematical Sciences HBNI Chennai India University of Bergen Bergen Norway

A directed odd cycle transversal of a directed graph (digraph) D is a vertex set S that intersects every odd directed cycle of D. In the Directed Odd Cycle Transversal (DOCT) problem, the input consists of a digraph D and an integer k. The objective is to determine whether there exists a directed odd cycle transversal of D of size at most k. In this paper, we settle the parameterized complexity of DOCT when parameterized by the solution size k by showing that DOCT does not admit an algorithm with running time f(k)nO(1) unless FPT = W[1]. On the positive side, we give a factor 2 fixed parameter tractable (FPT) approximation algorithm for the problem. More precisely, our algorithm takes as input D and k, runs in time 2O(k2)nO(1), and either concludes that D does not have a directed odd cycle transversal of size at most k, or produces a solution of size at most 2k. Finally, we provide evidence that there exists ϵ >0 such that DOCT does not admit a factor (1 + ϵ ) FPT-approximation algorithm. Copyright © 2017, The Authors. All rights reserved.

关键词： Directed graphs