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

Placing Green Bridges Optimally, with a Multivariate Analysis

THEORY OF COMPUTING SYSTEMS 2024年第5期68卷 1312-1338页

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

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 and study them from a computational complexity and parameterized algorithmics perspective.

关键词： Wildlife crossings Computational sustainability parameterized algorithmics NP-hardness Connected subgraphs

来源：评论

学校读者我要写书评

暂无评论

Disentangling the Computational Complexity of Network Untangling

引用

THEORY OF COMPUTING SYSTEMS 2024年第1期68卷 103-121页

作者： Froese, Vincent Kunz, Pascal Zschoche, Philipp Tech Univ Berlin Algorithm & Computat Complex Ernst Reuter Pl 7 D-10587 Berlin Germany Humboldt Univ Algorithm Engn Rudower Chaussee 25 D-12489 Berlin Germany

We study the network untangling problem introduced by Rozenshtein et al. (Data Min. Knowl. Disc. 35(1), 213-247, 2021), which is a variant of Vertex Cover on temporal graphs-graphs whose edge set changes over discrete time steps. They introduce two problem variants. The goal is to select at most k time intervals for each vertex such that all time-edges are covered and (depending on the problem variant) either the maximum interval length or the total sum of interval lengths is minimized. This problem has data mining applications in finding activity timelines that explain the interactions of entities in complex networks. Both variants of the problem are NP-hard. In this paper, we initiate a multivariate complexity analysis involving the following parameters: number of vertices, lifetime of the temporal graph, number of intervals per vertex, and the interval length bound. For both problem versions, we (almost) completely settle the parameterized complexity for all combinations of those four parameters, thereby delineating the border of fixed-parameter tractability.

关键词： Temporal graph mining parameterized algorithmics Complexity dichotomy

来源：评论

学校读者我要写书评

暂无评论

Multivariate algorithmics for eliminating envy by donating goods

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2024年第2期38卷 1-35页

作者： Boehmer, Niclas Bredereck, Robert Heeger, Klaus Knop, Dusan Luo, Junjie Tech Univ Berlin Algorithm & Computat Complex Berlin Germany Tech Univ Clausthal Inst Informat Clausthal Zellerfeld Germany Czech Tech Univ Prague Czech Republic Beijing Jiaotong Univ Beijing Peoples R China

Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary-encoded and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

关键词： Fair allocation Indivisible resources Envy-freeness Donating goods parameterized algorithmics

来源：评论

学校读者我要写书评

暂无评论

Multistage Vertex Cover

引用

THEORY OF COMPUTING SYSTEMS 2022年第2期66卷 454-483页

作者： Fluschnik, Till Niedermeier, Rolf Rohm, Valentin Zschoche, Philipp Tech Univ Berlin Algorithm & Computat Complex Berlin Germany

The NP-complete Vertex Cover problem asks to cover all edges of a graph by a small (given) number of vertices. It is among the most prominent graph-algorithmic problems. Following a recent trend in studying temporal graphs (a sequence of graphs, so-called layers, over the same vertex set but, over time, changing edge sets), we initiate the study of Multistage Vertex Cover. Herein, given a temporal graph, the goal is to find for each layer of the temporal graph a small vertex cover and to guarantee that two vertex cover sets of every two consecutive layers differ not too much (specified by a given parameter). We show that, different from classic Vertex Cover and some other dynamic or temporal variants of it, Multistage Vertex Cover is computationally hard even in fairly restricted settings. On the positive side, however, we also spot several fixed-parameter tractability results based on some of themost natural parameterizations.

关键词： parameterized algorithmics NP-completeness Temporal graphs Data reduction

来源：评论

学校读者我要写书评

暂无评论

Exploiting Database Management Systems and Treewidth for Counting

引用

THEORY AND PRACTICE OF LOGIC PROGRAMMING 2022年第1期22卷 128-157页

作者： Fichte, Johannes. K. K. Hecher, Markus Thier, Patrick Woltran, Stefan Univ Calif Berkeley Berkeley CA 94720 USA TU Wien Vienna Austria

Bounded treewidth is one of the most cited combinatorial invariants in the literature. It was also applied 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 (DBMSs). 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 DBMSs naturally allow for dealing with huge tables with a limited amount of main memory (RAM).

关键词： dynamic programming parameterized algorithmics bounded treewidth database systems SQL relational algebra counting

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

parameterized Complexity of Min-Power Asymmetric Connectivity

引用

THEORY OF COMPUTING SYSTEMS 2020年第7期64卷 1158-1182页

作者： Bentert, Matthias Haag, Roman Hofer, Christian Koana, Tomohiro Nichterlein, Andre TU Berlin Fac IV Algorithm & Computat Complex Berlin Germany

We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-weighted graph, MinPAC asks for a strongly connected spanning subgraph minimizing the summed vertex costs. Here, the cost of each vertex is the weight of its heaviest outgoing arc in the chosen subgraph. We present linear-time algorithms for the cases where the number of strongly connected components in a so-called obligatory subgraph or the feedback edge number in the underlying undirected graph is constant. Complementing these results, we prove that the problem is W[2]-hard with respect to the solution cost, even on restricted graphs with one feedback arc and binary arc weights.

关键词： Monitoring areas Reconnecting sensor networks parameterized algorithmics

来源：评论

学校读者我要写书评

暂无评论

Modification-fair cluster editing

引用

SOCIAL NETWORK ANALYSIS AND MINING 2024年第1期14卷 109-109页

作者： Froese, Vincent Kellerhals, Leon Niedermeier, Rolf Tech Univ Berlin Algorithm & Computat Complex Berlin Germany

The classic Cluster Editing problem (also known as Correlation Clustering) asks to transform a given graph into a disjoint union of cliques (clusters) by a small number of edge modifications. When applied to vertex-colored graphs (the colors representing subgroups), standard algorithms for the NP-hard Cluster Editing problem may yield solutions that are biased towards subgroups of data (e.g., demographic groups), measured in the number of modifications incident to the members of the subgroups. We propose a modification fairness constraint which ensures that the number of edits incident to each subgroup is proportional to its size. To start with, we study Modification-Fair Cluster Editing for graphs with two vertex colors. We show that the problem is NP-hard even if one may only insert edges within a subgroup;note that in the classic "non-fair" setting, this case is trivially polynomial-time solvable. However, in the more general editing form, the modification-fair variant remains fixed-parameter tractable with respect to the number of edge edits. We complement these and further theoretical results with an empirical analysis of our model on real-world social networks where we find that the price of modification-fairness is surprisingly low, that is, the cost of optimal modification-fair solutions differs from the cost of optimal "non-fair" solutions only by a small percentage.

关键词： Algorithmic fairness Cluster editing Correlation clustering parameterized algorithmics Price of fairness

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：