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

Exact algorithms for Clustered Planarity with Linear Saturators 35

学校读者我要写书评

暂无评论

Exact Algorithms for Clustered Planarity with Linear Saturat...

35th International Symposium on algorithms and Computation, ISAAC 2024

作者： Da Lozzo, Giordano Ganian, Robert Gupta, Siddharth Mohar, Bojan Ordyniak, Sebastian Zehavi, Meirav Roma Tre University Italy Algorithms and Complexity Group TU Wien Austria BITS Pilani K K Birla Goa Campus India Department of Mathematics Simon Fraser University Burnaby Canada University of Leeds United Kingdom Ben-Gurion University of the Negev Beer-Sheva Israel

ISBN: (纸本)9783959773546

We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an n-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths - one for each cluster - that connect all the vertices in each cluster while maintaining planarity. We show that the problem can be solved in time 2O(n) for both the variable and fixed embedding case. Moreover, we show that it can be solved in subexponential time 2O(√n log n) in the fixed embedding case if additionally the input graph is connected. The latter time complexity is tight under the Exponential-Time Hypothesis. We also show that n can be replaced with the vertex cover number of the input graph by providing a linear (resp. polynomial) kernel for the variable-embedding (resp. fixed-embedding) case;these results contrast the NP-hardness of the problem on graphs of bounded treewidth (and even on trees). Finally, we complement known lower bounds for the problem by showing that Clustered Planarity with Linear Saturators is NP-hard even when the number of clusters is at most 3, thus excluding the algorithmic use of the number of clusters as a parameter. © Giordano Da Lozzo, Robert Ganian, Siddharth Gupta, Bojan Mohar, Sebastian Ordyniak, and Meirav Zehavi.

关键词： Graph embeddings

Near-Tight Runtime Guarantees for Many-Objective Evolutionary algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wietheger, Simon Doerr, Benjamin Algorithms and Complexity Group Technische Universität Wien Vienna Austria CNRS École Polytechnique Institut Polytechnique de Paris Palaiseau France

Despite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing bounds for the SEMO, global SEMO, and SMS-EMOA algorithms on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we prove near-tight runtime guarantees for these three algorithms on the four most common benchmark problems OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJump, and this for arbitrary numbers of objectives. Our bounds depend only linearly on the Pareto front size, showing that these MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. Our bounds are tight apart from small polynomial factors in the number of objectives and length of bitstrings. This is the first time that such tight bounds are proven for many-objective uses of these MOEAs. While it is known that such results cannot hold for the NSGA-II, we do show that our bounds, via a recent structural result, transfer to the NSGA-III algorithm. Copyright © 2024, The Authors. All rights reserved.

关键词： Evolutionary algorithms

Computing Twin-Width Parameterized by the Feedback Edge Number

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Balabán, Jakub Ganian, Robert Rocton, Mathis Faculty of Informatics Masaryk University Brno Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria

The problem of whether and how one can compute the twin-width of a graph—along with an accompanying contraction sequence—lies at the forefront of the area of algorithmic model theory. While significant effort has been aimed at obtaining a fixed-parameter approximation for the problem when parameterized by twin-width, here we approach the question from a different perspective and consider whether one can obtain (near-)optimal contraction sequences under a larger parameterization, notably the feedback edge number k. As our main contributions, under this parameterization we obtain (1) a linear bikernel for the problem of either computing a 2-contraction sequence or determining that none exists and (2) an approximate fixed-parameter algorithm which computes an -contraction sequence (for an arbitrary specified ) or determines that the twin-width of the input graph is at least . These algorithmic results rely on newly obtained insights into the structure of optimal contraction sequences, and as a byproduct of these we also slightly tighten the bound on the twin-width of graphs with small feedback edge number. © 2023, CC BY.

关键词： Parameterization

Learning Depth Vision-Based Personalized Robot Navigation From Dynamic Demonstrations in Virtual Reality

学校读者我要写书评

暂无评论

Learning Depth Vision-Based Personalized Robot Navigation Fr...

IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

作者： Jorge de Heuvel Nathan Corral Benedikt Kreis Jacobus Conradi Anne Driemel Maren Bennewitz Humanoid Robots Lab Group for Algorithms and Complexity University of Bonn Lamarr Institute for Machine Learning and Artificial Intelligence Germany

For the best human-robot interaction experience, the robot's navigation policy should take into account personal preferences of the user. In this paper, we present a learning framework complemented by a perception pipeline to train a depth vision-based, personalized navigation controller from user demonstrations. Our virtual reality interface enables the demonstration of robot navigation trajectories under motion of the user for dynamic interaction scenarios. The novel perception pipeline enrolls a variational autoencoder in combination with a motion predictor. It compresses the perceived depth images to a latent state representation to enable efficient reasoning of the learning agent about the robot's dynamic environment. In a detailed analysis and ablation study, we evaluate different configurations of the perception pipeline. To further quantify the navigation controller's quality of personalization, we develop and apply a novel metric to measure preference reflection based on the Frechet Distance. We discuss the robot's navigation performance in various virtual scenes and demonstrate the first personalized robot navigation controller that solely relies on depth images. A supplemental video highlighting our approach is available online 1 1 Full video: ***/publications/deheuve123iros_***4.

关键词：

Further Exploiting c-Closure for FPT algorithms and Kernels for Domination Problems 39

学校读者我要写书评

暂无评论

Further Exploiting c-Closure for FPT Algorithms and Kernels ...

39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022

作者： Kanesh, Lawqueen Madathil, Jayakrishnan Roy, Sanjukta Sahu, Abhishek Saurabh, Saket National University of Singapore Singapore Chennai Mathematical Institute India Algorithms and Complexity Group TU Wien Austria The Institute of Mathematical Sciences HBNI Chennai India University of Bergen Norway

ISBN: (纸本)9783959772228

For a positive integer c, a graph G is said to be c-closed if every pair of non-adjacent vertices in G have at most c - 1 neighbours in common. The closure of a graph G, denoted by cl(G), is the least positive integer c for which G is c-closed. The class of c-closed graphs was introduced by Fox et al. [ICALP ‘18 and SICOMP ‘20]. Koana et al. [ESA ‘20] started the study of using cl(G) as an additional structural parameter to design kernels for problems that are W-hard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set and (Threshold) Dominating Set, and showed that each of these problems admits a polynomial kernel, either w.r.t. the parameter k + c or w.r.t. the parameter k for each fixed value of c. Here, k is the solution size and c = cl(G). The work of Koana et al. left several questions open, one of which was whether the Perfect Code problem admits a fixed-parameter tractable (FPT) algorithm and a polynomial kernel on c-closed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixed-parameter tractable w.r.t. the parameter k + cl(G), whereas Partial Dominating Set, parameterized by k is W[1]-hard even when cl(G) = 2. We also show that for each fixed c, Perfect Code admits a polynomial kernel on the class of c-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs, unless NP ⊆ co-NP/poly. © Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh.

关键词： Graphic methods

A Simple Partially Embedded Planarity Test Based on Vertex-Addition

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Fink, Simon D. Rutter, Ignaz Sandhya, T.P. Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Informatics and Mathematics University of Passau Germany Stockholm University Department of Mathematics Sweden

In the Partially Embedded Planarity problem, we are given a graph G together with a topological drawing of a subgraph H of G. The task is to decide whether the drawing can be extended to a drawing of the whole graph such that no two edges cross. Angelini et al. gave a linear-time algorithm for solving this problem in 2010 [1,2]. While their paper constitutes a significant result, the algorithm described therein is highly complex: it uses several layers of decompositions according to connectivity of both G and H, its description spans more than 30 pages, and can hardly be considered implementable. We give an independent linear-time algorithm that works along the well-known vertex-addition planarity test by Booth and Lueker [5,6]. We modify the PC-tree as underlying data structure used for representing all planar drawing possibilities in a natural way to also respect the restrictions given by the prescribed drawing of the subgraph H. The testing algorithm and its proof of correctness only require small adaptations from the comparatively much simpler generic planarity test, of which several implementations exist. If the test succeeds, an embedding can be constructed using the same approaches that are used for the generic planarity test. © 2024, CC BY-SA.

关键词： Trees (mathematics)

MosaicSets: Embedding Set Systems into Grid Graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Rottmann, Peter Wallinger, Markus Bonerath, Annika Gedicke, Sven Nöllenburg, Martin Haunert, Jan-Henrik The Geoinformation Group of the University of Bonn Germany The Algorithms and Complexity Group of the Technical University of Vienna Austria

Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets: a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews. © 2022, CC BY.

关键词： Visualization

Explaining Decisions in ML Models: a Parameterized complexity Analysis

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ordyniak, Sebastian Paesani, Giacomo Rychlicki, Mateusz Szeider, Stefan School of Computing University of Leeds United Kingdom Dipartimento di Informatica Sapienza University of Rome Italy Algorithms and Complexity Group TU Wien Vienna Austria

This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the prevalent black-box perception, our study focuses on models with transparent internal mechanisms. We address two principal types of explanation problems: abductive and contrastive, both in their local and global variants. Our analysis encompasses diverse ML models, including Decision Trees, Decision Sets, Decision Lists, Ordered Binary Decision Diagrams, Random Forests, and Boolean Circuits, and ensembles thereof, each offering unique explanatory challenges. This research fills a significant gap in explainable AI (XAI) by providing a foundational understanding of the complexities of generating explanations for these models. This work provides insights vital for further research in the domain of XAI, contributing to the broader discourse on the necessity of transparency and accountability in AI systems. Copyright © 2024, The Authors. All rights reserved.

关键词： Decision trees

Pseudorandom Finite Models

学校读者我要写书评

暂无评论

Pseudorandom Finite Models

Annual Symposium on Logic in Computer Science

作者： Jan Dreier Jamie Tucker-Foltz Algorithms and Complexity Group TU Wien Vienna Austria School of Engineering and Applied Sciences Harvard University Allston MA USA

We study pseudorandomness and pseudorandom generators from the perspective of logical definability. Building on results from ordinary derandomization and finite model theory, we show that it is possible to deterministically construct, in polynomial time, graphs and relational structures that are statistically indistinguishable from random structures by any sentence of first order or least fixed point logics. This raises the question of whether such constructions can be implemented via logical transductions from simpler structures with less entropy. In other words, can logical formulas be pseudorandom generators? We provide a complete classification of when this is possible for first order logic, fixed point logic, and fixed point logic with parity, and provide partial results and conjectures for first order logic with parity.

关键词：