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

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan 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 University of Leeds School of Computing Leeds United Kingdom

Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular. Interestingly, these problems can be equivalently formulated as classical graph problems on induced subgraphs of powers of partially-defined hypercubes. In this paper, we follow up on this recent direction by investigating the Independent Set problem on this graph class, which has been studied in the data science setting under the name Diversity. We obtain a comprehensive picture of the problem’s parameterized complexity and establish its fixed-parameter tractability w.r.t. the solution size plus the power of the hypercube. Given that several such FO-definable problems have been shown to be fixed-parameter tractable on the considered graph class, one may ask whether fixed-parameter tractability could be extended to capture all FO-definable problems. We answer this question in the negative by showing that FO model checking on induced subgraphs of hypercubes is as difficult as FO model checking on general graphs. © 2024, CC BY.

关键词： Model checking

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.

关键词：

The parameterized complexity of clustering incomplete data

学校读者我要写书评

暂无评论

arXiv 2019年

We study fundamental clustering problems for incomplete data. Specifically, given a set of incomplete d-dimensional vectors (representing rows of a matrix), the goal is to complete the missing vector entries in a way that admits a partitioning of the vectors into at most k clusters with radius or diameter at most r. We give tight characterizations of the parameterized complexity of these problems with respect to the parameters k, r, and the minimum number of rows and columns needed to cover all the missing entries. We show that the considered problems are fixed-parameter tractable when parameterized by the three parameters combined, and that dropping any of the three parameters results in parameterized intractability. A byproduct of our results is that, for the complete data setting, all problems under consideration are fixed-parameter tractable parameterized by k + r. Copyright © 2019, The Authors. All rights reserved.

关键词： Parameterization

Finding a Cluster in Incomplete Data

学校读者我要写书评

暂无评论

arXiv 2023年

We study two variants of the fundamental problem of finding a cluster in incomplete data. In the problems under consideration, we are given a multiset of incomplete d-dimensional vectors over the binary domain and integers k and r, and the goal is to complete the missing vector entries so that the multiset of complete vectors either contains (i) a cluster of k vectors of radius at most r, or (ii) a cluster of k vectors of diameter at most r. We give tight characterizations of the parameterized complexity of the problems under consideration with respect to the parameters k, r, and a third parameter that captures the missing vector entries. © 2023, CC BY.

关键词： Vectors

Progress on partial edge drawings

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2017年第4期21卷 757-786页

作者： Bruckdorfer, Till Cornelsen, Sabine Gutwenger, Carsten Kaufmann, Michael Montecchiani, Fabrizio Nöllenburg, Martin Wolff, Alexander Universität Tübingen Germany Universität Konstanz Germany Universität Dortmund Germany Università degli Studi di Perugia Italy Algorithms and Complexity Group TU Wien Vienna Austria Lehrstuhl für Informatik I Universität Würzburg Germany

Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been introduced. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on symmetric partial edge drawings (SPEDs) that require the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge’s existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction δ of the edge lengths (δ-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub. We show that, for a fixed stub-edge length ratio δ, not all graphs have a δ-SHPED. Specifically, we show that K165 does not have a 1/4-SHPED, while bandwidth-k graphs always have a Θ(1√k)-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem MaxSPED where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem of minimizing the total amount of erased ink. © 2017, Brown University. All rights reserved.

关键词： Graph theory

Parameterized algorithms for Coordinated Motion Planning: Minimizing Energy

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Deligkas, Argyrios Eiben, Eduard Ganian, Robert Kanj, Iyad Ramanujan, M.S. 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 the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of k robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously-established results that were restricted to solid grids. We design a fixed-parameter additive approximation algorithm for this problem parameterized by k alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied coordinated motion planning problems: (1) A fixed-parameter algorithm, parameterized by k, for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle;and (2) a fixed-parameter algorithm, parameterized by k plus the treewidth of the input graph, for the standard Coordinated Motion Planning (CMP) problem in which we need to route all the k robots to their destinations. The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by k on graphs of bounded outerplanarity, which include bounded-height subgrids. We complement the above results with a lower bound which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts the recently-obtained tractability of the problem on solid grids under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth - a class including, among others, all graphs of bounded genus. Copyright © 2024, The Authors. All rights reserved.

关键词： Parameterization

Graph drawing applications in combinatorial theory of maturity models

学校读者我要写书评

暂无评论

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

Detours in Directed Graphs

学校读者我要写书评

暂无评论

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