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

Towards Optimal and Expressive Kernelization for d-Hitting Set

ALGORITHMICA 2014年第1期70卷 129-147页

作者： van Bevern, Rene TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

A sunflower in a hypergraph is a set of hyperedges pairwise intersecting in exactly the same vertex set. Sunflowers are a useful tool in polynomial-time data reduction for problems formalizable as d-Hitting Set, the problem of covering all hyperedges (whose cardinality is bounded from above by a constant d) of a hypergraph by at most k vertices. Additionally, in fault diagnosis, sunflowers yield concise explanations for "highly defective structures". We provide a linear-time algorithm that, by finding sunflowers, transforms an instance of d-Hitting Set into an equivalent instance comprising at most O(k (d) ) hyperedges and vertices. In terms of parameterized complexity, we show a problem kernel with asymptotically optimal size (unless ) and provide experimental results that show the practical applicability of our algorithm. Finally, we show that the number of vertices can be reduced to O(k (d-1)) with additional processing in O(k (1.5d) ) time-nontrivially combining the sunflower technique with problem kernels due to Abu-Khzam and Moser.

关键词： parameterized algorithmics Linear-time data reduction Vertex cover in hypergraphs Fault diagnosis Sunflower lemma Algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Cluster editing with locally bounded modifications

引用

DISCRETE APPLIED MATHEMATICS 2012年第15期160卷 2259-2270页

作者： Komusiewicz, Christian Uhlmann, Johannes TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

Given an undirected graph G = (V, E) and a nonnegative integer k, the NP-hard CLUSTER EDITING problem asks whether G can be transformed into a disjoint union of cliques by modifying at most k edges. In this work, we study how "local degree bounds" influence the complexity Of CLUSTER EDITING and of the related CLUSTER DELETION problem which allows only edge deletions. We show that even for graphs with constant maximum degree CLUSTER EDITING and CLUSTER DELETION are NP-hard and that this implies NP-hardness even if every vertex is incident with only a constant number of edge modifications. We further show that under some complexity-theoretic assumptions both CLUSTER EDITING and CLUSTER DELETION cannot be solved within a running time that is subexponential in k, vertical bar V vertical bar, or vertical bar E vertical bar. Finally, we present a problem kernelization for the combined parameter "number d of clusters and maximum number t of modifications incident with a vertex" thus showing that CLUSTER EDITING and CLUSTER DELETION become easier in case the number of clusters is upper-bounded. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Graph modification problems parameterized algorithmics Exponential-time hypothesis Data reduction

来源：评论

学校读者我要写书评

暂无评论

REFLECTIONS ON MULTIVARIATE algorithmics AND PROBLEM PARAMETERIZATION

REFLECTIONS ON MULTIVARIATE ALGORITHMICS AND PROBLEM PARAMET...

引用

27th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Niedermeier, Rolf Friedrich Schiller Univ Jena Inst Informat Ernst Abbe Pl 2 D-07743 Jena Germany

ISBN: (纸本)9783939897163

Research on parameterized algorithmics for NP-hard problems has steadily grown over the last years. We survey and discuss how parameterized complexity analysis naturally develops into the field of multivariate algorithmics. Correspondingly, we describe how to perform a systematic investigation and exploitation of the "parameter space" of computationally hard problems.

关键词： Algorithmsand Complexity parameterized algorithmics Coping with Computational Intractability Fixed-Parameter Tractability

来源：评论

学校读者我要写书评

暂无评论

Placing Green Bridges Optimally, with a Multivariate Analysis 1

引用

17th Conference on Computability in Europe (CiE)

作者： Fluschnik, Till Kellerhals, Leon Tech Univ Berlin Algorithm & Computat Complex Fac 4 Berlin Germany

ISBN: (数字)9783030800499

ISBN: (纸本)9783030800499;9783030800482

We study the problem of placing wildlife crossings, such as green bridges, over human-made obstacles to challenge habitat fragmentation. The main task herein is, given a graph describing habitats or routes of wildlife animals and possibilities of building green bridges, to find a low-cost placement of green bridges that connects the habitats. We develop three problem models for this task, which model different ways of how animals roam their habitats. We settle the classical complexity and parameterized complexity (regarding the number of green bridges and the number of habitats) of the three problems.

关键词： Wildlife crossings Computational complexity Computational sustainability parameterized algorithmics Connected subgraphs

来源：评论

学校读者我要写书评

暂无评论

Exploiting Database Management Systems and Treewidth for Counting 22nd

Exploiting Database Management Systems and Treewidth for Cou...

引用

22nd International Symposium on Practical Aspects of Declarative Languages (PADL)

作者： Fichte, Johannes K. Hecher, Markus Thier, Patrick Woltran, Stefan Tech Univ Dresden Dresden Germany TU Wien Vienna Austria Univ Potsdam Potsdam Germany

ISBN: (纸本)9783030391973;9783030391966

Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #Sat, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #Sat often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMS). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMS naturally allow to deal with huge tables with a limited amount of main memory (RAM), parallelization, as well as suspending computation.

关键词： Dynamic programming parameterized algorithmics Bounded treewidth Database systems SQL Relational algebra Counting

来源：评论

学校读者我要写书评

暂无评论

An Improved GPU-Based SAT Model Counter 25th

An Improved GPU-Based SAT Model Counter

引用

25th International Conference on the Principles and Practice of Constraint Programming (CP)

作者： Fichte, Johannes K. Hecher, Markus Zisser, Markus Tech Univ Dresden Dresden Germany TU Wien Vienna Austria Univ Potsdam Potsdam Germany

ISBN: (纸本)9783030300487

In this paper, we present and evaluate a new parallel propositional model counter, called gpusat2, which is based on dynamic programming (DP) on tree decompositions using log-counters. gpusat2 extends its predecessor by a novel architecture for DP that includes using customized tree decompositions, storing solutions to parts of the input instance during the computation variably in arrays or binary search trees, and compressing solution parts. In addition, we avoid data transfer between the RAM and the VRAM whenever possible and employ extended preprocessing by means of state-of-the-art preprocessors for propositional model counting. Our novel architecture allows gpusat2 to be competitive with modern model counters when we also take preprocessing into consideration. As a side result, we observe that state-of-the-art preprocessors allow to produce tree decompositions of significantly smaller width.

关键词： Propositional model counting Dynamic programming parameterized algorithmics Bounded treewidth

来源：评论

学校读者我要写书评

暂无评论

Confluence in Data Reduction: Bridging Graph Transformation and Kernelization

引用

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE 2013年第1期2卷 31-49页

作者： Ehrig, Hartmut Ermel, Claudia Hueffner, Falk Niedermeier, Rolf Runge, Olga Inst Softwaretechnik & Theoret Informat TU Berlin Sekr MAR 5-5Marchstr 23 D-10587 Berlin Germany

Kernelization is a core tool of parameterized algorithmics for coping with computationally intractable problems. A kernelization reduces in polynomial time an input instance to an equivalent instance whose size is bounded by a function only depending on some problem-specific parameter k;this new instance is called problem kernel. Typically, problem kernels are achieved by performing efficient data reduction rules. So far, there was little systematic study in the literature concerning the mutual interaction of data reduction rules, in particular whether data reduction rules for a specific problem always lead to the same reduced instance, no matter in which order the rules are applied. This corresponds to the concept of confluence from the theory of rewriting systems. We argue that it is valuable to study whether a kernelization is confluent, using the NP-hard graph problems (EDGE) CLIQUE COVER and PARTIAL CLIQUE COVER as running examples. We apply the concept of critical pair analysis from graph transformation theory, supported by the AGG software tool. These results support the main goal of our work, namely, to establish a fruitful link between (parameterized) algorithmics and graph transformation theory, two so far unrelated fields.

关键词： parameterized algorithmics problem kernel formal methods critical pair analysis confluence

来源：评论

学校读者我要写书评

暂无评论

On Generating Triangle-Free Graphs

引用

Electronic Notes in Discrete Mathematics 2009年第C期32卷 51-58页

作者： Brügmann, Daniel Komusiewicz, Christian Moser, Hannes Institut für Informatik Friedrich-Schiller-Universität Jena D-07743 Jena Ernst-Abbe-Platz 2 Germany

We show that the problem to decide whether a graph can be made triangle-free with at most k edge deletions remains NP-complete even when restricted to planar graphs of maximum degree seven. In addition, we provide polynomial-time data reduction rules for this problem and obtain problem kernels consisting of 6k vertices for general graphs and 11k/3 vertices for planar graphs. © 2009 Elsevier B.V. All rights reserved.

关键词： kernelization NP-complete problem parameterized algorithmics

来源：评论

学校读者我要写书评

暂无评论

The parameterized Complexity of Welfare Guarantees in Schelling Segregation 24

The Parameterized Complexity of Welfare Guarantees in Schell...

引用

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

作者： Argyrios Deligkas Eduard Eiben Tiger-Lily Goldsmith Royal Holloway University of London Egham United Kingdom

ISBN: (纸本)9798400704864

Schelling's model considers k types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers neighboring agents of the same type. We are motivated by a recent line of work that studies solutions that are optimal with respect to notions related to the welfare of the agents. We explore the parameterized complexity of computing such solutions. We focus on the well-studied notions of social welfare (WO) and Pareto optimality (PO), alongside the recently proposed notions of group-welfare optimality (GWO) and utility-vector optimality (UVO), both of which lie between WO and ¶O. Firstly, we focus on the fundamental case where k=2 and there are r red agents and b blue agents. We show that all solution-notions we consider are intractable even when b=1 and that they do not admit an FPT algorithm when parameterized by r and b, unless FPT = W[1]. In addition, we show that WO and GWO remain intractable even on cubic graphs. We complement these negative results with an FPT algorithm parameterized by r, b and the maximum degree of the graph. For the general case with k types of agents, we prove that for any of the notions we consider the problem remains hard when parameterized by k for a large family of graphs that includes trees. We accompany these negative results with an XP algorithm parameterized by k and the treewidth of the graph.

关键词： parameterized algorithmics schelling welfare maximization

来源：评论

学校读者我要写书评

暂无评论

A refined complexity analysis of fair districting over graphs

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2023年第1期37卷 13-13页

作者： Boehmer, Niclas Koana, Tomohiro Niedermeier, Rolf Tech Univ Berlin Algorithm & Computat Complex D-10623 Berlin Germany

We study the NP-hard Fair Connected Districting problem recently proposed by Stoica et al. [AAMAS 2020]: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. Herein, one strives for "fair districts " without any type being in a dominating majority in any of the districts. This is to e.g. prevent segregation or political domination of some political party. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting. In particular, we prove that it is polynomial-time solvable on paths, cycles, stars, and caterpillars, but already becomes NP-hard on trees. Motivated by the latter negative result, we perform a parameterized complexity analysis with respect to various graph parameters including treewidth, and problem-specific parameters, including, the numbers of colors and districts. We obtain a rich and diverse, close to complete picture of the corresponding parameterized complexity landscape (that is, a classification along the complexity classes FPT, XP, W[1]-hard, and para-NP-hard).

关键词： parameterized algorithmics Electoral Districting Fairness Social Choice on Social Networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：