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

41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016

作者： Ganian, Robert De Haan, Ronald Kanj, Iyad Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria School of Computing DePaul University ChicagoIL United States

ISBN: (纸本)9783959770163

Impagliazzo et al. proposed a framework, based on the logic fragment defining the complexity class SNP, to identify problems that are equivalent to k-CNF-Sat modulo subexponential-time reducibility (serf-reducibility). The subexponential-time solvability of any of these problems implies the failure of the Exponential Time Hypothesis (ETH). In this paper, we extend the framework of Impagliazzo et al., and identify a larger set of problems that are equivalent to k- CNF-Sat modulo serf-reducibility. We propose a complexity class, referred to as Linear Monadic NP, that consists of all problems expressible in existential monadic second order logic whose expressions have a linear measure in terms of a complexity parameter, which is usually the universe size of the problem. This research direction can be traced back to Fagin's celebrated theorem stating that NP coincides with the class of problems expressible in existential second order logic. Monadic NP, a well-studied class in the literature, is the restriction of the aforementioned logic fragment to existential monadic second order logic. The proposed class Linear Monadic NP is then the restriction of Monadic NP to problems whose expressions have linear measure in the complexity parameter. We show that Linear Monadic NP includes many natural complete problems such as the satisfiability of linear-size circuits, dominating set, independent dominating set, and perfect code. Therefore, for any of these problems, its subexponential-time solvability is equivalent to the failure of ETH. We prove, using logic games, that the aforementioned problems are inexpressible in the monadic fragment of SNP, and hence, are not captured by the framework of Impagliazzo et al. Finally, we show that Feedback Vertex Set is inexpressible in existential monadic second order logic, and hence is not in Linear Monadic NP, and investigate the existence of certain reductions between Feedback Vertex Set (and variants of it) and 3-CNF-Sat. © Cody Geary

关键词： Computer circuits

来源：评论

学校读者我要写书评

暂无评论

Hedonic Diversity Games: A complexity Picture with More than Two Colors 36

Hedonic Diversity Games: A Complexity Picture with More than...

引用

36th AAAI Conference on Artificial Intelligence, AAAI 2022

作者： Ganian, Robert Hamm, Thekla Knop, Dušan Schierreich, Šimon Suchý, Ondřej Algorithms and Complexity Group TU Wien Austria Faculty of Information Technology Czech Technical University Prague Czech Republic

ISBN: (纸本)1577358767

Hedonic diversity games are a variant of the classical Hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexity-theoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a complete parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general Hedonic diversity games where the number of colors is not necessarily restricted to two, and show that-apart from two trivial cases-a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question posed in previous work. © 2022, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

Towards a polynomial kernel for directed feedback vertex set 42

Towards a polynomial kernel for directed feedback vertex set

引用

42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017

作者： Bergougnoux, Benjamin Eiben, Eduard Ganian, Robert Ordyniak, Sebastian Ramanujan, M.S. Université Clermont Auvergne LIMOS CNRS Aubière France Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959770460

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008];since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus. © Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan;licensed under Creative Commons License CC-BY.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Worbel: Aggregating Point Labels into Word Clouds 21

Worbel: Aggregating Point Labels into Word Clouds

引用

29th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2021

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Science Education and Research Bhopal Bhopal India Algorithms and Complexity Group Tu Wien Vienna Austria

ISBN: (纸本)9781450386647

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster. © 2021 ACM.

关键词： Visualization

来源：评论

学校读者我要写书评

暂无评论

Extending partial 1-planar drawings 47

Extending partial 1-planar drawings

引用

47th International Colloquium on Automata, Languages, and Programming, ICALP 2020

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Klute, Fabian Nöllenburg, Martin Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959771382

Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph theory and graph drawing. In such an extension problem, we are given a tuple (G, H, H) consisting of a graph G, a connected subgraph H of G and a drawing H of H, and the task is to extend H into a drawing of G while maintaining some desired property of the drawing, such as planarity. In this paper we study the problem of extending partial 1-planar drawings, which are drawings in the plane that allow each edge to have at most one crossing. In addition we consider the subclass of IC-planar drawings, which are 1-planar drawings with independent crossings. Recognizing 1-planar graphs as well as IC-planar graphs is NP-complete and the NP-completeness easily carries over to the extension problem. Therefore, our focus lies on establishing the tractability of such extension problems in a weaker sense than polynomial-time tractability. Here, we show that both problems are fixed-parameter tractable when parameterized by the number of edges missing from H, i.e., the edge deletion distance between H and G. The second part of the paper then turns to a more powerful parameterization which is based on measuring the vertex+edge deletion distance between the partial and complete drawing, i.e., the minimum number of vertices and edges that need to be deleted to obtain H from G. © Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, and Martin Nöllenburg;licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

SAT-Based Generation of Planar Graphs 26

SAT-Based Generation of Planar Graphs

引用

26th International Conference on Theory and Applications of Satisfiability Testing, SAT 2023

作者： Markus Kirchweger Manfred Scheucher Stefan Szeider Algorithms and Complexity Group TU Wien Austria Institut för Mathematik Technische Universität Berlin Germany

ISBN: (纸本)9783959772860

To test a graph's planarity in SAT-based graph generation we develop SAT encodings with dynamic symmetry breaking as facilitated in the SAT modulo Symmetry (SMS) framework. We implement and compare encodings based on three planarity criteria. In particular, we consider two eager encodings utilizing order-based and universal-set-based planarity criteria, and a lazy encoding based on Kuratowski's theorem. The performance and scalability of these encodings are compared on two prominent problems from combinatorics: The computation of planar Turán numbers and the Earth-Moon problem. We further showcase the power of SMS equipped with a planarity encoding by verifying and extending several integer sequences from the Online Encyclopedia of Integer Sequences (OEIS) related to planar graph enumeration. Furthermore, we extend the SMS framework to directed graphs which might be of independent interest. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Moon

来源：评论

学校读者我要写书评

暂无评论

A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)

A Mathematical Runtime Analysis of the Non-dominated Sorting...

引用

2024 Genetic and Evolutionary Computation Conference Companion, GECCO 2024 Companion

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

ISBN: (纸本)9798400704956

The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. While it performs evidently well on bi-objective optimization problems, empirical studies suggest that it is less effective when applied to problems with more than two objectives. A recent mathematical runtime analysis confirmed this observation by proving that the NGSA-II for an exponential number of iterations misses a constant factor of the Pareto front of the simple m-objective OneMinMax problem when m ≥ *** this work, we provide the first mathematical runtime analysis of the NSGA-III, a refinement of the NSGA-II aimed at better handling more than two objectives. We prove that the NSGA-III with sufficiently many reference points - a small constant factor more than the size of the Pareto front, as suggested for this algorithm - computes the complete Pareto front of the 3-objective OneMinMax benchmark in an expected number of O(n log n) iterations. This result holds for all population sizes (that are at least the size of the Pareto front). It shows a drastic advantage of the NSGA-III over the NSGA-II on this *** paper for the Hot-off-the-Press track at GECCO 2024 summarizes the work Simon Wietheger and Benjamin Doerr. A mathematical runtime analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III). In International Joint Conference on Artificial Intelligence, IJCAI 2023. 5657 - 5665, 2023. [15]. © 2024 Copyright held by the owner/author(s).

关键词： Genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

Lossy kernels for hitting subgraphs 42

Lossy kernels for hitting subgraphs

引用

42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017

作者： Eiben, Eduard Hermelin, Danny Ramanujan, M.S. Algorithms and Complexity Group TU Wien Vienna Austria Industrial Engineering and Management Ben Gurion University Be'er Scheva Israel

ISBN: (纸本)9783959770460

In this paper, we study the Connected H-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the Connected H-hitting set problem, we obtain an -approximate kernel for every > 1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the Dominating Set problem on d-degenerate graphs, and provide an interpolation of approximate kernels between the known d2-approximate kernel of constant size and 1-approximate kernel of size kO(d2). © Eduard Eiben, Danny Hermelin, and M. S. Ramanujan;licensed under Creative Commons License CC-BY.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Splitting Plane Graphs to Outerplanarity

引用

Journal of Graph algorithms and Applications 2024年第3期28卷 31-48页

作者： Gronemann, Martin Nöllenburg, Martin Villedieu, Anaïs Algorithms and Complexity Group TU Wien Vienna Austria

Vertex splitting replaces a vertex by two copies and partitions its incident edges amongst the copies. This problem has been studied as a graph editing operation to achieve desired properties with as few splits as possible, most often planarity, for which the problem is NP-hard. Here we study how to minimize the number of splits to turn a plane graph into an outerplane one. We tackle this problem by establishing a direct connection between splitting a plane graph to outerplanarity, finding a connected face cover, and finding a feedback vertex set in its dual. We prove NP-completeness for plane biconnected graphs, while we show that a polynomial-time algorithm exists for maximal planar graphs. Additionally, we show upper and lower bounds for certain families of maximal planar graphs. Finally, we provide a SAT formulation for the problem, and evaluate it on a small benchmark. © 2024, Brown University. All rights reserved.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

A linear-Time parameterized algorithm for node unique label cover 25

A linear-Time parameterized algorithm for node unique label ...

引用

25th European Symposium on algorithms, ESA 2017

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

ISBN: (纸本)9783959770491

The optimization version of the Unique Label Cover problem is at the heart of the Unique Games Conjecture which has played an important role in the proof of several tight inapproximability results. In recent years, this problem has been also studied extensively from the point of view of parameterized complexity. Chitnis et al. [FOCS 2012, SICOMP 2016] proved that this problem is fixed-parameter tractable (FPT) and Wahlström [SODA 2014] gave an FPT algorithm with an improved parameter dependence. Subsequently, Iwata, Wahlström and Yoshida [SICOMP 2016] proved that the edge version of Unique Label Cover can be solved in linear FPT-Time, and they left open the existence of such an algorithm for the node version of the problem. In this paper, we resolve this question by presenting the first linear-Time FPT algorithm for Node Unique Label Cover.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：