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

Extension of some edge graph problems: Standard, parameterized and approximation complexity

DISCRETE APPLIED MATHEMATICS 2023年第1期340卷 183-201页

作者： Casel, Katrin Fernau, Henning Ghadikolaei, Mehdi Khosravian Monnot, Jerome Sikora, Florian Univ Potsdam Hasso Plattner Inst D-14482 Potsdam Germany Univ Trier Fachbereich 4 Informat Wissensch D-54296 Trier Germany PSL Univ Univ Paris Dauphine CNRS LAMSADE F-75016 Paris France

We consider extension variants of some edge optimization problems in graphs containing the classical EDGE COVER, MATCHING, and EDGE DOMINATING SET problems and generaliza-tions thereof. Given a graph G = (V, E) and an edge set U c E, it is asked whether there exists an inclusion-wise minimal (or maximal, respectively) feasible solution E & PRIME;which satisfies a given property, for instance, being an edge dominating set (or a matching, respectively) and containing the forced edge set U (or avoiding any edges from the forbidden edge set E \ U, respectively). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counter-balance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation and inapproximability results.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Extension problems Edge cover Matching Edge domination NP-completeness parameterized complexity Approximation

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of manipulating Top Trading Cycles

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2022年第2期36卷 51-51页

作者： Phan, William Purcell, Christopher North Carolina State Univ Dept Econ Raleigh NC 27695 USA Univ West Bohemia Dept Math Plzen Czech Republic

We study the problem of exchange when agents are endowed with heterogeneous indivisible objects, and there is no money. In this setting, no rule satisfies Pareto-efficiency, individual rationality, and strategy-proof/less;there is no consensus in the literature on satisfactory second-best mechanisms. A natural generalization of the ubiquitous Top Trading Cycles (TTC) satisfies the first two properties on the lexicographic domain, rendering it manipulable. We characterize the computational complexity of manipulating this mechanism;we show that it is W[P]-hard by reduction from MONOTONE WEIGHTED CIR-CUIT SATISFIABILITY. We provide a matching upper bound for a wide range of preference domains. We further show that manipulation by groups (when parameterized by group size) is W[P]-hard. This provides support for TTC as a second-best mechanism. Lastly, our results are of independent interest to complexity theorists: there are few natural W[P]-complete problems and, as far as we are aware, this is the first such problem arising from the social sciences.

关键词： Top trading cycles parameterized complexity Manipulation

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Asynchronous Border Minimization

引用

ALGORITHMICA 2019年第1期81卷 201-223页

作者： Ganian, Robert Kronegger, Martin Pfandler, Andreas Popa, Alexandru Johannes Kepler Univ Linz Linz Austria TU Wien Vienna Austria Univ Bucharest Bucharest Romania Univ Siegen Siegen Germany Natl Inst Res & Dev Informat Bucharest Romania

Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). The common task of these two problems is to create so-called probe sequences (essentially a string) in a microarray. Here, the goal of the former problem is to determine an assignment of each probe sequence to a unique cell of the array and afterwards to construct the sequences at their respective cells while minimizing the border length of the probes. In contrast, for the latter problem the assignment of the probes to the cells is already given. In this paper we investigate the parameterized complexity of the natural exhaustive variants of BMP and P-BMP, termed BMPe and P-BMPe respectively, under several natural parameters. We show that BMPe and P-BMPe are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input () and the number of rows of the microarray (r);and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMPe is in FPT when parameterized by c and . We complement our tractability results with a number of corresponding hardness results.

关键词： parameterized complexity Fixed-parameter tractability NP-hard problem Microarrays

来源：评论

学校读者我要写书评

暂无评论

Integer programming in parameterized complexity: Five miniatures

引用

DISCRETE OPTIMIZATION 2022年第Part1期44卷

作者： Gavenciak, Tomas Koutecky, Martin Knop, Dusan Charles Univ Prague Comp Sci Inst Fac Math & Phys Malostranske Namesti 25 Prague Czech Republic Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Thakurova 9 Prague Czech Republic

Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f (k)poly(n). We focus on: Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter;we show which algorithms and tricks are often useful for speed-ups. Minding the poly(n): reducing f (k) often has the unintended consequence of increasing poly(n);so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Capacitated Dominating Set, Sum Coloring, Max-q-Cut, and certain other coloring problems by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, indefinite quadratic programs in fixed dimension, parametric integer programs in fixed dimension, and 2-stage stochastic integer programs. (C) 2020

关键词： Graph coloring Sum-coloring parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of Welfare Guarantees in Schelling Segregation 23

The Parameterized Complexity of Welfare Guarantees in Schell...

引用

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

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

ISBN: (纸本)9781450394321

Schelling's model considers k types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers neighbor 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 and Pareto optimality, alongside the recently proposed notions of group-welfare optimality and utility-vector optimality.

关键词： schelling parameterized complexity welfare maximization

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of [1, j]-domination problems

引用

THEORETICAL COMPUTER SCIENCE 2020年 804卷 207-218页

作者： Meybodi, Mohsen Alambardar Fomin, Fedor, V Mouawad, Amer E. Panolan, Fahad Univ Isfahan Dept Appl Math & Comp Sci POB 81746 Esfahan 73441 Iran Univ Bergen Dept Informat Bergen Norway Amer Univ Beirut Comp Sci Dept Beirut Lebanon IIT Hyderabad Dept Comp Sci & Engn Sangareddy 502285 Telangana India

For a graph G, a set D subset of V (G) is called a [1. j)-dominating set if every vertex in V (G) \ D has at least one and at most j neighbors in D. A set D subset of V(G) is called a [1, j)-total dominating set if every vertex in V(G) has at least one and at most j neighbors in D. In the [1, j]-(TOTAL) DOMINATING SET problem we are given a graph G and a positive integer k. The objective is to test whether there exists a [1, j]-(total) dominating set of size at most k. The [1, j]-DOMINATING SET problem is known to be NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The [1, 2]-TOTAL DOMINATING SET problem is known to be NP-complete, even for bipartite graphs. As both problems generalize the DOMINATING SET problem, both are W[1]-hard when parameterized by solution size. In this work, we study the aforementioned problems on various graph classes from the perspective of parameterized complexity and prove the following results: [1, j]-DOMINATING SET parameterized by solution size is W[1]-hard on d-degenerate graphs for d = j +1. [1, j]-DOMINATING SET parameterized by solution size is FPT on nowhere dense graphs. The known algorithm for [1, j]-DOMINATING SET on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH). Assuming SETH, we provide a lower bound for the running time of any algorithm solving the [1, 2]-TOTAL DOMINATING SET problem parameterized by pathwidth. Finally, we study another variant Of DOMINATING SET, called RESTRAINED DOMINATING SET, that asks if there is a dominating set D of G of size at most k such that no vertex outside of D has all of its neighbors in D. We prove this variant is W[1]-hard even on 3-degenerate graphs. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Dominating set [1, j]-dominating set Total dominating set Restrained dominating set parameterized complexity Sparse graphs

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of 2-partitions

引用

THEORETICAL COMPUTER SCIENCE 2020年 844卷 97-105页

作者： Andersen, J. B. Bang-Jensen, J. Yeo, A. Univ Southern Denmark Dept Math & Comp Sci Odense Denmark

We give an FPT algorithm for deciding whether the vertex set of a digraph D can be partitioned into two disjoint sets V-1, V-2 such that the digraph D[V-1] induced by V-1 has a vertex that can reach all other vertices by directed paths, the digraph D[V-2] has no vertex of in-degree zero and vertical bar V-i vertical bar >= k(i), where k(1) k(2) are part of the input. This settles an open problem from [1,4]. (C) 2020 Elsevier B.V. All rights reserved.

关键词： FPT algorithm Out-branching 2-partition Directed graph parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity and kernelization of resilience for database queries

引用

THEORETICAL COMPUTER SCIENCE 2020年 840卷 199-211页

作者： Miao, Dongjing Li, Jianzhong Cai, Zhipeng Harbin Inst Technol Sch Comp Sci & Technol Harbin 150000 Heilongjiang Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

Given a database instance and a query on it whose result is initially non-empty, the resilience decision problem is to decide if there exist a small enough number of facts in the database instance such that the deletion of these facts empties the result of the given query. In this paper, we revisit the resilience decision problem. We investigate the parameterized complexity for various classes of database queries. We consider the factors including the query size and the number of variables, and present several intractable cases even from the perspective of parameterized complexity. Meanwhile, we refine the characteristics of resilience for self-join-free conjunctive queries containing triads, and show that it is still NP-hard even if the structure of the input database instance is simple. This result implies the hardness essentially comes from the parity of triangle sequence instead of the complicate (non-planar) intersections of cycles. On the other hand, we also obtain some positive results showing that the resilience decision problem is still fixed parameter tractable for an important case through kernelization. Our work demonstrates a new insight for employing resilience computation in database operations. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Resilience Conjunctive query parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Graph Modification to First-Order Logic Properties

引用

THEORY OF COMPUTING SYSTEMS 2020年第2期64卷 251-271页

作者： Fomin, Fedor V. Golovach, Petr A. Thilikos, Dimitrios M. Univ Bergen Dept Informat Bergen Norway Univ Montpellier AlGCo Project Team CNRS LIRMM Montpellier France

We establish connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order logic formula phi, we consider the problem of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the resulting modification has the property expressible by phi. We provide sufficient and necessary conditions on the structure of the prefix of phi specifying when the corresponding graph modification problem is fixed-parameter tractable (parameterized by k) and when it admits a polynomial kernel.

关键词： First-order logic Graph modification parameterized complexity Descriptive complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

A parameterized view on the complexity of dependence and independence logic

引用

JOURNAL OF LOGIC AND COMPUTATION 2022年第8期32卷 1624-1644页

作者： Kontinen, Juha Meier, Arne Mahmood, Yasir Univ Helsinki Dept Math & Stat PL 68 Helsinki 00014 Finland Leibniz Univ Hannover Inst Theoret Informat D-30167 Hannover Germany

In this paper, we investigate the parameterized complexity of model checking for Dependence and Independence logic, which are well studied logics in the area of Team Semantics. We start with a list of nine immediate parameterizations for this problem, namely the number of disjunctions (i.e. splits)/(free) variables/universal quantifiers, formula-size, the tree-width of the Gaifman graph of the input structure, the size of the universe/team and the arity of dependence atoms. We present a comprehensive picture of the parameterized complexity of model checking and obtain a division of the problem into tractable and various intractable degrees. Furthermore, we also consider the complexity of the most important variants (data and expression complexity) of the model checking problem by fixing parts of the input.

关键词： Team semantics dependence logic independence logic parameterized complexity model checking

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：