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

37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017

作者： Agrawal, Akanksha Krithika, R. Lokshtanov, Daniel Mouawad, Amer E. Ramanujan, M.S. Department of Informatics University of Bergen Bergen Norway Institute of Mathematical Sciences HBNI Chennai India Algorithms and Complexity Group Vienna University of Technology Vienna Austria

ISBN: (纸本)9783959770552

For a family of graphs F, an n-vertex graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A (multi) graph G = (V, ?ai=1Ei), where the edge set of G is partitioned into a color classes, is called an a-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored graphs is the Simultaneous (F1, . . ., Fa)-Deletion problem. In the latter problem, we are given an a-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph Gi - S, where Gi = (V, Ei) and 1 = i = a, is in Fi. Recently, a subset of the authors considered the aforementioned problem with F1 = . . . = Fa being the family of all forests. They showed that the problem is fixed-parameter tractable when parameterized by k and a and can be solved in O(2O(ak)) time1. In this work, we initiate the investigation of the complexity of Simultaneous (F1, . . ., Fa)-Deletion with di erent families of graphs. In the process, we obtain a complete characterization of the parameterized complexity of this problem when one or more of the Fis is the class of bipartite graphs and the rest (if any) are forests. We show that if F1 is the family of all bipartite graphs and each of F2 = F3 = . . . = Fa is the family of all forests then the problem is fixed-parameter tractable parameterized by k and a. However, even when F1 and F2 are both the family of all bipartite graphs, then the Simultaneous (F1, F2)-Deletion problem itself is already W[1]-hard. © Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, and M. S. Ramanujan.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Minimizing crossings in constrained two-sided circular graph layouts

arXiv

引用

arXiv 2018年

作者： Klute, Fabian Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one-page and two-page book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct half-planes (the pages) bounded by the spine. In this paper we study the problem of minimizing the crossings for a fixed cyclic vertex order by computing an optimal k-plane set of exteriorly drawn edges for k ≥ 1, extending the previously studied case k = 0. We show that this relates to finding bounded-degree maximum-weight induced subgraphs of circle graphs, which is a graph-theoretic problem of independent interest. We show NP-hardness for arbitrary k, present an efficient algorithm for k = 1, and generalize it to an explicit XP-time algorithm for any fixed k. For the practically interesting case k = 1 we implemented our algorithm and present experimental results that confirm the applicability of our algorithm. Copyright © 2018, The Authors. All rights reserved.

关键词： Drawing (graphics)

来源：评论

学校读者我要写书评

暂无评论

On Erdős–Szekeres-type problems for k-convex point sets

引用

European Journal of Combinatorics 2020年 89卷 103157-103157页

作者： Balko, Martin Bhore, Sujoy Martínez-Sandoval, Leonardo Valtr, Pavel Department of Applied Mathematics Charles University Prague Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria Institut de Mathématiques de Jussieu – Paris Rive Gauche (UMR 7586) Sorbonne Université Paris France Faculty of Sciences National Autonomous University of Mexico Mexico City Mexico

We study Erdős–Szekeres-type problems for k-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set S of n points is k-convex if there exists a spanning simple polygonization of S such that the intersection of any straight line with its interior consists of at most k connected components. We address several open problems about k-convex point sets. In particular, we extend the well-known Erdős–Szekeres Theorem by showing that, for every fixed k∈N, every set of n points in the plane in general position (with no three collinear points) contains a k-convex subset of size at least Ω(log^kn). We also show that there are arbitrarily large 3-convex sets of n points in the plane in general position whose largest 1-convex subset has size O(logn). This gives a solution to a problem posed by Aichholzer et al. (2014). We prove that there is a constant c>0 such that, for every n∈N, there is a set S of n points in the plane in general position such that every 2-convex polygon spanned by at least c⋅logn points from S contains a point of S in its interior. This matches an earlier upper bound by Aichholzer et al. (2014) up to a multiplicative constant and answers another of their open problems. © 2020 Elsevier Ltd

关键词：

来源：评论

学校读者我要写书评

暂无评论

The power of cut-based parameters for computing edge disjoint paths

arXiv

引用

arXiv 2018年

作者： Ganian, Robert Ordyniak, Sebastian Algorithms and Complexity group TU Wien Vienna Austria Algorithms group University of Sheffield Sheffield United Kingdom

This paper revisits the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in P in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter treecut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded treecut width. Our second result shows that EDP parameterized by treecut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph. Copyright © 2018, The Authors. All rights reserved.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Geometric Planar Networks on Bichromatic Collinear Points

arXiv

引用

arXiv 2019年

作者： Bandyapadhyay, Sayan Banik, Aritra Bhore, Sujoy Nöllenburg, Martin Department of Informatics University of Bergen Norway School of Computer Sciences NISER Bhubaneswar India Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group Technische Universität Wien Austria

We study three classical graph problems – Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems for collinear points. We show that almost all of these problems can be solved in linear time in this setting. © 2019, CC BY.

关键词： Hamiltonians

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: Treewidth modulator: Emergency exit for DFVS 45

Brief announcement: Treewidth modulator: Emergency exit for ...

引用

45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

作者： Lokshtanov, Daniel Ramanujan, M.S. Saurabh, Saket Sharma, Roohani Zehavi, Meirav Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences HBNI UMI ReLax India Department of Computer Science Ben-Gurion University Israel

ISBN: (纸本)9783959770767

In the Directed Feedback Vertex Set (DFVS) problem, we are given as input a directed graph D and an integer k, and the objective is to check whether there exists a set S of at most k vertices such that F = D − S is a directed acyclic graph (DAG). Determining whether DFVS admits a polynomial kernel (parameterized by the solution size) is one of the most important open problems in parameterized complexity. In this article, we give a polynomial kernel for DFVS parameterized by the solution size plus the size of any treewidth-η modulator, for any positive integer η. We also give a polynomial kernel for the problem, which we call Vertex Deletion to treewidth-η DAG, where given as input a directed graph D and a positive integer k, the objective is to decide whether there exists a set of at most k vertices, say S, such that D − S is a DAG and the treewidth1 of D − S is at most η. © 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

The complexity landscape of decompositional parameters for ILP

arXiv

引用

arXiv 2018年

作者： Ganian, Robert Ordyniak, Sebastian Algorithms and Complexity Group TU Wien Favoritenstrasse 9-11 Wien1040 Austria

Integer Linear Programming (ILP) can be seen as the archetypical problem for NP-complete optimization problems, and a wide range of problems in artificial intelligence are solved in practice via a translation to ILP. Despite its huge range of applications, only few tractable fragments of ILP are known, probably the most prominent of which is based on the notion of total unimodularity. Using entirely different techniques, we identify new tractable fragments of ILP by studying structural parameterizations of the constraint matrix within the framework of parameterized complexity. In particular, we show that ILP is fixed-parameter tractable when parameterized by the treedepth of the constraint matrix and the maximum absolute value of any coefficient occurring in the ILP instance. Together with matching hardness results for the more general parameter treewidth, we give an overview of the complexity of ILP w.r.t. decompositional parameters defined on the constraint matrix. Copyright © 2018, The Authors. All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

On structural parameterizations of the edge disjoint paths problem 28

On structural parameterizations of the edge disjoint paths p...

引用

28th International Symposium on algorithms and Computation, ISAAC 2017

作者： Ganian, Robert Ordyniak, Sebastian Sridharan, Ramanujan Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959770545

In this paper we revisit the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our focus lies on structural parameterizations for the problem that allow for efficient (polynomial-Time or fpt) algorithms. As our first result, we answer an open question stated in Fleszar, Mnich, and Spoerhase (2016), by showing that the problem can be solved in polynomial time if the input graph has a feedback vertex set of size one. We also show that EDP parameterized by the treewidth and the maximum degree of the input graph is fixed-parameter tractable. Having developed two novel algorithms for EDP using structural restrictions on the input graph, we then turn our attention towards the augmented graph, i.e., the graph obtained from the input graph after adding one edge between every terminal pair. In constrast to the input graph, where EDP is known to remain NP-hard even for treewidth two, a result by Zhou et al. (2000) shows that EDP can be solved in non-uniform polynomial time if the augmented graph has constant treewidth;we note that the possible improvement of this result to an fpt-Algorithm has remained open since then. We show that this is highly unlikely by establishing the W[1]-hardness of the problem parameterized by the treewidth (and even feedback vertex set) of the augmented graph. Finally, we develop an fpt-Algorithm for EDP by exploiting a novel structural parameter of the augmented graph.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of clustering incomplete data

arXiv

引用

arXiv 2019年

作者： 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

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

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for the matrix completion problem

arXiv

引用

arXiv 2018年

作者： Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Austria School of Computing DePaul University Chicago United States

We consider two matrix completion problems, in which we are given a matrix with missing entries and the task is to complete the matrix in a way that (1) minimizes the rank, or (2) minimizes the number of distinct rows. We study the parameterized complexity of the two aforementioned problems with respect to several parameters of interest, including the minimum number of matrix rows, columns, and rows plus columns needed to cover all missing entries. We obtain new algorithmic results showing that, for the bounded domain case, both problems are fixed-parameter tractable with respect to all aforementioned parameters. We complement these results with a lower-bound result for the unbounded domain case that rules out fixed-parameter tractability w.r.t. some of the parameters under consideration. Copyright © 2018, The Authors. All rights reserved.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：