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

TARGET SET SELECTION IN DENSE GRAPH CLASSES

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第1期36卷 536-572页

作者： Dvorak, Pavel Knop, Dusan Toufar, Tomas Charles Univ Prague Inst Comp Sci Prague 11636 Czech Republic Czech Tech Univ Fac Informat Technol Prague 16000 Czech Republic Charles Univ Prague Fac Math & Phys Prague 11636 Czech Republic

In this paper, we study the TARGET SET SELECTION problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex, the task is to find a set of vertices (called a target set) that activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to half of its neighbors (the so-called MAJORITY TARGET SET SELECTION problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the MAJORITY TARGET SET SELECTION problem when parameterized by (a restriction of) the modular-width -a natural generalization of both previous structural parameters. We also show the TARGET SET SELECTION problem parameterized by the neighborhood diversity or by the twin cover number is W[1]-hard when there is no restriction on the thresholds.

关键词： parameterized complexity target set selection dense graphs opinion diffusion

来源：评论

学校读者我要写书评

暂无评论

SUBEXPONENTIAL parameterized ALGORITHMS FOR PLANAR AND APEX-MINOR-FREE GRAPHS VIA LOW

引用

SIAM JOURNAL ON COMPUTING 2022年第6期51卷 1866-1930页

作者： Fomin, Fedor, V Lokshtanov, Daniel Marx, Daniel Pilipczuk, Marcin Pilipczuk, Michal Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA CISPA Helmholtz Ctr Informat Secur Saarland Informat Campus D-66123 Saarbrucken Germany Univ Warsaw Inst Informat PL-02097 Warsaw Poland Inst Math Sci Chennai 600113 India

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: A induces a subgraph of G of treewidth O( k log k), and for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2\scrO ( k log2 k) . n\scrO (1)) - 1, where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential-time parameterized algorithms for problems on planar graphs, usually with running time bound 2\scrO ( k log2 k)n\scrO (1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host LOCAL SEARCH, and SUBGRAPH ISOMORPHISM, among others. Up to this point, it was open whether these problems could be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

关键词： parameterized complexity subexponential algorithms treewidth planar graphs subgraph isomorphism

来源：评论

学校读者我要写书评

暂无评论

Extension Perfect Roman Domination 11th

Extension Perfect Roman Domination

引用

11th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2025

作者： Mann, Kevin Fernau, Henning Universität Trier Fachbereich 4 – Abteilung Informatikwissenschaften Trier54286 Germany

ISBN: (纸本)9783031834370

For an introductory single lecture into parameterized complexity classes, it appears to be necessary to introduce different problems to capture the (most important) different levels of the W-hierarchy. This puts an additional burden on the audience, as they also have to understand the different problems and not only the different complexity classes. In this paper, we will show that Extension Perfect Roman Domination, EXTPRD for short, is a single problem that can be used for this introductory purpose. We can characterize the classes W[1], W[2] and W[3] and find problems in FPT, XP and those being para-NP-hard. Also, it can be used to explain how the choice of the parameter can influence the complexity status of the problem. One can even touch fine-grained complexity by establishing a run-time lower bound based on the k-Orthogonal Vector conjecture. Ext PRD, being a sibling to Roman Domination, also comes with a nice story that can be also seen from the perspective of adventure games and might hence be appealing. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： (Perfect) Roman domination parameterized complexity W[3]

来源：评论

学校读者我要写书评

暂无评论

Games That Cannot Go on Forever! Active Participation in Research Is the Main Issue for Kids 7th

Games That Cannot Go on Forever! Active Participation in Res...

引用

7th International Conference on Creative Mathematical Sciences Communication, CMSC 2024

作者： Fellows, Michael R. Rosamond, Frances A. Lebanese American University Beirut Lebanon

ISBN: (纸本)9783031732560

It is entirely interesting, and profoundly important to science, that efforts to communicate science have often led scientists to new perspectives on their own work and their scientific fields and specialties. This two-way street in science communication was a founding impulse and inspiration of the Creative Mathematical Sciences Communication (CMSC) conference series. The vigor of that impulse continues in this paper via a few new game horizons. This paper uses well-quasi-ordering of trees and other mathematical objects to create games that are easy to understand, addictive, and engage some powerful mathematical fundamentals. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： Artificial Intelligence Games Mathematical Sciences Communication parameterized complexity Well-Quasi-Ordering

来源：评论

学校读者我要写书评

暂无评论

parameterized Algorithms for Covering by Arithmetic Progressions 49th

Parameterized Algorithms for Covering by Arithmetic Progress...

引用

49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Bliznets, Ivan Nederlof, Jesper Szilagyi, Krisztina Univ Groningen Groningen Netherlands Univ Utrecht Utrecht Netherlands

ISBN: (纸本)9783031521126;9783031521133

An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressions, called COVER BY ARITHMETIC PROGRESSIONS (CAP) and EXACT COVER BY ARITHMETIC PROGRESSIONS (XCAP). In both problems, we are given a set X consisting of n integers along with an integer k, and our goal is to find k arithmetic progressions whose union is X. In XCAP we additionally require the arithmetic progressions to be disjoint. Both problems were shown to be NP-complete by Heath [IPL'90]. We present a 2(O(k2)) poly(n) time algorithm for CAP and a 2(O(k3)) poly(n) time algorithm for XCAP. We also give a fixed parameter tractable algorithm for CAP parameterized below some guaranteed solution size. We complement these findings by proving that CAP is Strongly NP-complete in the field Z(p), if p is a prime number part of the input.

关键词： Arithmetic Progressions Set Cover parameterized complexity Number Theory

来源：评论

学校读者我要写书评

暂无评论

Distance Vector Domination 50th

Distance Vector Domination

引用

50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025

作者： Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. Department of Psychology University of Campania "L.Vanvitelli" Caserta Italy Department of Computer Science University of Salerno Fisciano Italy

ISBN: (纸本)9783031826696

Identifying and mitigating the spread of fake information is a challenging issue that has become dominant with the rise of social media. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, once immunized, can prevent the spreading of fake narratives. The considered problem, named Distance Vector Domination generalizes both distance and multiple domination, at individual (i.e., vertex) level. We study the parameterized complexity of the problem according to several standard and structural parameters. We prove the W[1]-hardness of the problem with respect to neighborhood diversity, even when all the distances are 1. We also give fixed-parameter algorithms for some variants of the problem and parameter combinations. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： Distance Domination Modular-width Neighborhood diversity parameterized complexity Treewidth Vector Domination

来源：评论

学校读者我要写书评

暂无评论

Introducing lop-Kernels: A Framework for Kernelization Lower Bounds

引用

ALGORITHMICA 2022年第11期84卷 3365-3406页

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

In the MAXIMUM MINIMAL VERTEX COVER (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain kernelization lower bounds for a certain type of kernels for optimization problems, which we call lop-kernels. Informally, this type of kernel is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. Discrete Appl Math 196:62-71, 2015. https://***/10.1016/***. 2014.06.001), and that the known cubic kernel for MAXIMUM MINIMAL FEEDBACK VERTEX SET is also essentially optimal. We present further applications for TREE DELETION SET and for MAXIMUM INDEPENDENT SET on K-t-free graphs. Back to the MMVC problem, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdos-Hajnal property. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless N P subset of coN P / poly.

关键词： parameterized complexity Polynomial kernel Kernelization lower bound Maximum minimal vertex cover Erdos-Hajnal property Induced subgraphs

来源：评论

学校读者我要写书评

暂无评论

Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width

引用

ALGORITHMICA 2022年第11期84卷 3489-3520页

作者： Ducoffe, Guillaume Natl Inst Res & Dev Informat Bucharest Romania Univ Bucharest Bucharest Romania

Recently, independent groups of researchers have presented algorithms to compute a maximum matching in (O) over tilde (f (k) . (n + m)) time, for some computable function f, within the graphs where some clique-width upper bound is at most k (e.g., tree-width, modular-width and P4-sparseness). However, to the best of our knowledge, the existence of such algorithm within the graphs of bounded clique-width has remained open until this paper. Indeed, we cannot even apply Courcelle's theorem to this problem directly, because a matching cannot be expressed in MSO1 logic. Our first contribution is an almost linear-time algorithm to compute a maximum matching in any bounded clique-width graph, being given a corresponding clique-width expression. We also present how to compute the Edmonds-Gallai decomposition in almost linear time by using the same framework. For that, we do apply Courcelle's theorem but to the classic Tutte-Berge formula, that can easily be expressed as a CMSO1 optimization problem. Doing so, we can compute the cardinality of a maximum matching, but not the matching itself. To obtain with this approach a maximum matching, we need to combine it with a recursive dissection scheme for bounded clique-width graphs and with a distributed version of Courcelle's theorem (Courcelle and Vanicat, DAM 2016) - of which we present here a slightly stronger version than the standard one in the literature. Finally, for the bipartite graphs of clique-width at most k, we present an alternative (O) over tilde (k(2) . (n + m))-time algorithm for the problem. The algorithm is randomized and it is based on a completely different approach than above: combining various reductions to matching and flow problems on bounded tree-width graphs with a very recent result on the parameterized complexity of linear programming (Dong et. al., STOC'21). Our results for bounded clique-width graphs extend many prior works on the complexity of MAXIMUM MATCHING within cographs, distance-hereditary

关键词： Clique-width Clique parameterized complexity Bipartite graph Maximum matching

来源：评论

学校读者我要写书评

暂无评论

Spy game: FPT-algorithm, hardness and graph products

引用

THEORETICAL COMPUTER SCIENCE 2022年 923卷 304-317页

作者： Costa, Eurinardo Rodrigues Martins, Nicolas Almeida Sampaio, Rudini Univ Fed Ceara Campus Russas Russas Brazil Univ Integr Int Lusofonia Afrobrasileira Unilab Redencao Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil

In the (s, d)-spy game over a graph G, k guards and one spy occupy some vertices of G and, at each turn, the spy may move with speed s(along at most sedges) and each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy wins if she reaches a vertex at distance more than the surveilling distance d from every guard. This game was introduced by Cohen et al. (2016) [15] and is related to two wellstudied games: Cops and Robber game and Eternal Dominating game. The guard number gns,d(G) is the minimum number of guards such that the guards have a winning strategy (of controlling the spy) in the graph G. In 2018, it was proved that deciding if the spy has a winning strategy is NP-hard for every speed s >= 2and distance d >= 0. In this paper, we initiate the investigation of the guard number in grids and in graph products. We obtain a strict upper bound on the strong product of two general graphs and obtain examples with King grids that match this bound and other examples for which the guard number is smaller. We also obtain the exact value of the guard number in the lexicographical product of two general graphs for any distance d >= 2. From the algorithmic point of view, we prove a positive result: if the number k of guards is fixed, the spy game is solvable in polynomial XP time O(n(3k+2)) for every speed s >= 2and distance d = 0. In other words, the spy game is XP when parameterized by the number of guards. This XP algorithm is used to obtain an FPT algorithm on the P-4-fewness of the graph. As a negative result, we prove that the spy game is W[2]-hard even in bipartite graphs when parameterized by the number of guards, for every speed s >= 2and distance d >= 0, extending the hardness result of Cohen et al. in 2018. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Games on graphs Spy game Graph products XP algorithm parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Structural Parameterizations with Modulator Oblivion

引用

ALGORITHMICA 2022年第8期84卷 2335-2357页

作者： Jacob, Ashwin Panolan, Fahad Raman, Venkatesh Sahlot, Vibha HBNI Inst Math Sci Chennai Tamil Nadu India IIT Hyderabad Dept Comp Sci & Engn Hyderabad India Charles Univ Prague Comp Sci Inst CSI Prague 11800 Czech Republic

It is known that problems like VERTEX COVER, FEEDBACK VERTEX SET and ODD CYCLE TRANSVERSAL are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most k vertices whose deletion results in a chordal graph when parameterized by k. While this investigation fits naturally into the recent trend of what is called 'structural parameterizations', here we assume that the deletion set is not given. One method to solve them is to compute a k-sized or an approximate (f(k) sized, for a function f) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least k(O(k))n(O(1)) running time when we use the known parameterized or approximation algorithms for finding a k-sized chordal deletion set on an n vertex graph. In this work, we design 2(O(k))n(O(1)) time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in 2(O(k))n(O(1)) time where each bag is a union of four cliques and O(k) vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are, what are sometimes called permissive in the sense that given an integer k, they detect whether the graph has no chordal vertex deletion set of size at most k or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the strong exponential time hypothesis.

关键词： parameterized complexity Chordal graph Tree decomposition Strong exponential time hypothesis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：