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

parameterized complexity of Computing Maximum Minimal Blocking and Hitting Sets

ALGORITHMICA 2023年第2期85卷 444-491页

作者： Araujo, Julio Bougeret, Marin Campos, Victor A. Sau, Ignasi Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil Univ Montpellier LIRMM CNRS Montpellier France Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil

A blocking set in a graph G is a subset of vertices that intersects every maximum independent set of G. Let mmbs(G) be the size of a maximum (inclusion-wise) minimal blocking set of G. This parameter has recently played an important role in the kernelization of VERTEX COVER with structural parameterizations. We provide a panorama of the complexity of computing mmbs parameterized by the natural parameter and the independence number of the input graph. We also consider the closely related parameter mmhs, which is the size of a maximum minimal hitting set of a hypergraph. Finally, we consider the problem of computing mmbs parameterized by treewidth, especially relevant in the context of kernelization. Since a blocking set intersects every maximum-sized independent set of a given graph and properties involving counting the sizes of arbitrarily large sets are typically non-expressible in monadic second-order logic, its tractability does not seem to follow from Courcelle's theorem. Our main technical contribution is a fixed-parameter tractable algorithm for this problem.

关键词： Maximum minimal blocking set Maximum minimal hitting set parameterized complexity Treewidth Kernelization Vertex cover Upper domination

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of multi-node hubs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年 131卷 64-85页

作者： Saurabh, Saket Zehavi, Meirav HBNI Inst Math Sci Chennai India IRL 2000 ReLaX Chennai India Univ Bergen Bergen Norway Ben Gurion Univ Negev Beer Sheva Israel

Hubs are high-degree nodes within a network, ubiquitous in complex networks such as telecommunication, biological, social and semantic networks. Here, we do not seek a hub that is a single node, but a hub consisting of k nodes. Formally, given a graph G = (V, E), we a seek a set A subset of V of size k that induces a connected subgraph from which at least p edges emanate. Thus, we identify k nodes which can act as a unit (due to the connectivity constraint) that is a hub (due to the cut constraint). This problem, which we call MULTI-NODE HUB (MNH), is a variant of the classic MAX CUT problem. While it is easy to see that MNH is W[1]-hard with respect to the parameter k, our main contribution is a parameterized algorithm that shows that MNH is FPT with respect to the parameter p. (C) 2022 Elsevier Inc. All rights reserved.

关键词： Hub parameterized complexity Bisection decomposition

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Weighted Target Set Selection 18th

Parameterized Complexity of Weighted Target Set Selection

引用

18th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Suzuki, Takahiro Kimura, Kei Suzuki, Akira Tamura, Yuma Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Japan Kyushu Univ Fac Informat Sci & Elect Engn Fukuoka Japan

ISBN: (纸本)9789819723393;9789819723409

Consider a graph G where each vertex has a threshold. A vertex v in G is activated if the number of active vertices adjacent to v is at least as many as its threshold. A vertex subset A(0) of G is a target set if eventually all vertices in G are activated by initially activating vertices of A(0). The Target Set Selection problem (TSS) involves finding the smallest target set of G with vertex thresholds. This problem has already been extensively studied and is known to be NP-hard even for very restricted conditions. In this paper, we analyze TSS and its weighted variant, called the Weighted Target Set Selection problem (WTSS) from the perspective of parameterized complexity. Let k be the solution size and l be the maximum threshold. We first show that TSS is W[1]-hard for split graphs when parameterized by k + l, and W[2]-hard for cographs when parameterized by k. We also prove that WTSS is W[2]-hard for trivially perfect graphs when parameterized by k. On the other hand, we show that WTSS can be solved in O(n log n) time for complete graphs. Additionally, we design FPT algorithms for WTSS when parameterized by nd + l, tw + l, ce, and vc, where nd is the neighborhood diversity, tw is the treewidth, ce is the cluster editing number, and VC is the vertex cover number of the input graph.

关键词： parameterized complexity Graph algorithms Target set selection

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Directed Spanner Problems

引用

ALGORITHMICA 2022年第8期84卷 2292-2308页

作者： Fomin, Fedor, V Golovach, Petr A. Lochet, William Misra, Pranabendu Saurabh, Saket Sharma, Roohani Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany HBNI Inst Math Sci Chennai Tamil Nadu India

We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance between any two vertices in H is at most t times the distance between these vertices in G, that is, H keeps the distances in G up to the distortion (or stretch) factor t. An additive t-spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter t, that is, the distances in H and G differ by at most t. The task of Directed Multiplicative Spanner is, given a directed graph G with m arcs and positive integers t and k, decide whether G has amultiplicative t-spanner with at most m-k arcs. Similarly, Directed Additive Spanner asks whether G has an additive t-spanner with at most m-k arcs. We show that (i) Directed Multiplicative Spanner admits a polynomial kernel of size O(k(4)t(5)) and can be solved in randomized (4t)(k) . n(O(1)) time, (ii) the weighted variant of DIRECTED MULTIPLICATIVE SPANNER can be solved in k(2k) . n(O(1)) time on directed acyclic graphs, (iii) Directed Additive Spanner is W[1]-hard when parameterized by k for every fixed t >= 1 evenwhen the input graphs are restricted to be directed acyclic graphs. The latter claim contrasts with the recent result of Kobayashi from STACS 2020 that the problem for undirected graphs is FPT when parameterized by t and k.

关键词： Graph spanners Directed graphs parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

Group control for procedural rules:parameterized complexity and consecutive domains

引用

Frontiers of Computer Science 2024年第3期18卷 133-141页

作者： Yongjie YANG Dinko DIMITROV Chair of Economic Theory Saarland UniversitySaarbrücken 66123Germany

We consider GROUP CONTROL BY ADDING INDIVIDUALS(GCAI)in the setting of group identification for two procedural rules-the consensus-start-respecting rule and the liberal-start-respecting *** is known that GCAI for both rules are NP-hard,but whether they are fixed-parameter tractable with respect to the number of distinguished individuals remained *** resolve both open problems in the *** addition,we strengthen the NP-hardness of GCAI by showing that,with respect to the natural parameter the number of added individuals,GCAI for both rules are W[2]-***,the W[2]-hardness for the liberal-startrespecting rule holds even when restricted to a very special case where the qualifications of individuals satisfy the so-called consecutive ones ***,for the consensus-startrespecting rule,the problem becomes polynomial-time solvable in this special *** also study a dual restriction where the disqualifications of individuals fulfill the consecutive ones property,and show that under this restriction GCAI for both rules turn out to be polynomial-time *** reductions for showing W[2]-hardness also imply several algorithmic lowerbounds.

关键词： group control by adding individuals group identification parameterized complexity consecutive ones property FPT W[2]-hard

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of satisfactory partition problem

引用

THEORETICAL COMPUTER SCIENCE 2022年 907卷 113-127页

作者： Gaikwad, Ajinkya Maity, Soumen Tripathi, Shuvam Kant Indian Inst Sci Educ & Res Pune Maharashtra India

Given an undirected graph G, we study the SATISFACTORY PARTITION problem, where the goal is to decide whether it is possible to partition the vertex set of G into two parts such that each vertex has at least as many neighbours in its own part as in the other part. The BALANCED SATISFACTORY PARTITION problem is a variant of the above problem where the two partite sets are required to have the same cardinality. Both problems are known to be NP-complete. This problem was introduced by Gerber and Kobler (2000) [9] and further studied by other authors, but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The main results of the paper are the following: (1) SATISFACTORY PARTITION is polynomial-time solvable for block graphs, (2) SATISFACTORY PARTITION and BALANCED SATISFACTORY PARTITION are fixed parameter tractable (FPT) when parameterized by neighbourhood diversity. (3) SATISFACTORY PARTITION and its balanced version can be solved in polynomial time for graphs of bounded clique-width, and (4) BALANCED SATISFACTORY PARTITION is W[1]-hard when parameterized by treewidth. (C) 2022 Elsevier B.V. All rights reserved.

关键词： parameterized complexity FPT W[1]-hard Treewidth Clique-width Neighbourhood diversity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of two-interval pattern problem

引用

THEORETICAL COMPUTER SCIENCE 2022年 902卷 21-28页

作者： Bose, Prosenjit Mehrabi, Saeed Mondal, Debajyoti Carleton Univ Sch Comp Sci Ottawa ON Canada Mem Univ Comp Sci Dept St John NF Canada Univ Saskatchewan Dept Comp Sci Saskatoon SK Canada

A 2-interval is the union of two disjoint intervals on the real line. Two 2-intervals D1 and D2 are disjoint if their intersection is empty (i.e., no interval of D1 intersects any interval of D2). There can be three different relations between two disjoint 2-intervals;namely, preceding (<), nested (E) and crossing (0). Two 2-intervals D1 and D2 are called R-comparable for some R is an element of {<, E, 0}, if either D1R D2 or D2R D1. A set D of disjoint 2intervals is R-comparable, for some R subset of {<, E, 0} and R = empty set , if every pair of 2-intervals in D are R-comparable for some R is an element of R. Given a set of 2-intervals and some R subset of {<, E, 0}, the objective of the 2-interval pattern problem is to find a largest subset of 2-intervals that is R-comparable. The 2-interval pattern problem is known to be W[1]-hard when |R| = 3 and NP-hard when |R| = 2 (except for R = {<, E}, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing that it is W[1]-hard for both R = {E, 0} and R = {<, 0} (when parameterized by the size of an optimal solution). This answers the open question posed by Vialette ((2008) [22]).

关键词： Two-interval pattern Interval graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Propositional Inclusion and Independence Logic 1

引用

29th International Workshop on Logic, Language, Information and Computation (WoLLIC)

作者： Mahmood, Yasir Virtema, Jonni Paderborn Univ Dept Comp Sci DICE Grp Paderborn Germany Univ Sheffield Dept Comp Sci Sheffield S Yorkshire England

We give a comprehensive account on the parameterized complexity of model checking and satisfiability of propositional inclusion and independence logic. We discover that for most parameterizations the problems are eith... 详细信息

ISBN: (数字)9783031397844

ISBN: (纸本)9783031397837;9783031397844

关键词： Propositional Logic Team Semantics Model checking Satisfiability parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Graph Burning

引用

ALGORITHMICA 2022年第8期84卷 2379-2393页

作者： Kobayashi, Yasuaki Otachi, Yota Hokkaido Univ Sapporo Hokkaido Japan Nagoya Univ Nagoya Aichi Japan

GRAPH BURNING asks, given a graph G = (V, E) and an integer k, whether there exists (b(0), ...,b(k-1)) is an element of V-k such that every vertex in G has distance at most i from some b(i). This problem is known to be NP-complete even on connected caterpillars of maximum degree 3. We study the parameterized complexity of this problem and answer all questions by Kare and Reddy [IWOCA 2019] about the parameterized complexity of the problem. We show that the problem is W[2]-complete parameterized by k and that it does not admit a polynomial kernel parameterized by vertex cover number unless NP subset of coNP/poly. We also show that the problem is fixed-parameter tractable parameterized by clique-width plus the maximum diameter among all connected components. This implies the fixed-parameter tractability parameterized by modular-width, by treedepth, and by distance to cographs. Using a different technique, we show that parameterization by distance to split graphs is also tractable. We finally show that the problem parameterized by max leaf number is XP.

关键词： Graph burning parameterized complexity Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

On parameterized complexity of Binary Networked Public Goods Game

引用

ALGORITHMICA 2024年第1期86卷 307-333页

作者： Maiti, Arnab Dey, Palash IIT Kharagpur Kharagpur India

In the binary networked public goods (BNPG for short) game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the problem of deciding if there exists a pure strategy Nash equilibrium (PSNE) in such games. The problem is already known to be NP-complete. This casts doubt on predictive power of PSNE in BNPG games. We provide fine-grained analysis of this problem under the lens of parameterized complexity theory. We consider various natural graph parameters and show W[1]-hardness, XP, and FPT results. Hence, our work significantly improves our understanding of BNPG games where PSNE serves as a reliable solution concept. We finally prove that some graph classes, for example path, cycle, bi-clique, and complete graph, always have a PSNE if the utility function of the players are same.

关键词： parameterized complexity Pure staretgy nash equilibrium Binary networked public goods game

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：