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

50th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Bodlaender, Hans L. Szilagyi, Krisztina Univ Utrecht Utrecht Netherlands

ISBN: (纸本)9783031754081;9783031754098

The class XNLP consists of (parameterized) problems that can be solved nondeterministically in f(k)n(O(1)) time and g(k) log n space, where n is the size of the input instance and k the parameter. The class XALP consists of problems that can be solved in the above time and space with access to an additional stack. These two classes are a "natural home" for many standard graph problems and their generalizations. In this paper, we show the hardness of several problems on planar graphs, parameterized by outerplanarity, treewidth and pathwidth, thus strengthening several existing results. In particular, we show XNLP-hardness of the following problems parameterized by outerplanarity: ALL-OR-NOTHING FLOW, TARGET OUTDEGREE ORIENTATION, CAPACITATED (RED-BLUE) DOMINATING SET, TARGET SET SELECTION etc. We also show the XNLP-completeness of SCATTERED SET parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity.

关键词： parameterized complexity XNLP XALP Planar Graphs Outerplanarity

来源：评论

学校读者我要写书评

暂无评论

On Polynomial Kernelization for Stable Cutset 50th

On Polynomial Kernelization for Stable Cutset

引用

50th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Kratsch, Stefan Le, Van Bang Humboldt Univ Inst Informat Berlin Germany Univ Rostock Inst Informatik Rostock Germany

ISBN: (纸本)9783031754081;9783031754098

A stable cutset in a graph G is a set S subset of V (G) such that vertices of S are pairwise non-adjacent and such that G - S is disconnected, i.e., it is both stable (or independent) set and a cutset (or separator). Unlike general cutsets, it is NP-complete to determine whether a given graph G has any stable cutset. Recently, Rauch et al. [FCT 2023] gave a number of fixed-parameter tractable (FPT) algorithms, time f(k) . vertical bar V(G)vertical bar(c), for STABLE CUTSET under a variety of parameters k such as the size of a (given) dominating set, the size of an odd cycle transversal, or the deletion distance to P-5-free graphs. Earlier works imply FPT algorithms relative to clique-width and relative to solution size. We complement these findings by giving the first results on the existence of polynomial kernelizations for STABLE CUTSET, i.e., efficient pre-processing algorithms that return an equivalent instance of size polynomial in the parameter value. Under the standard assumption that NP not subset of coNP/poly, we show that no polynomial kernelization is possible relative to the deletion distance to a single path, generalizing deletion distance to various graph classes, nor by the size of a (given) dominating set. We also show that under the same assumption no polynomial kernelization is possible relative to solution size, i.e., given (G, k) answering whether there is a stable cutset of size at most k. On the positive side, we show polynomial kernelizations for parameterization by modulators to a single clique, to a cluster or a co-cluster graph, and by twin cover.

关键词： stable cutset kernelization parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Fast Winning Strategies for the Attacker in Eternal Domination 50th

Fast Winning Strategies for the Attacker in Eternal Dominati...

引用

50th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Bagan, Guillaume Bousquet, Nicolas Oijid, Nacim Pierron, Theo Univ Claude Bernard Lyon 1 CNRS INSA Lyon LIRISUMR5205 F-69622 Villeurbanne France

ISBN: (纸本)9783031754081;9783031754098

Dominating sets in graphs are often used to model monitoring problems, by posting guards on the vertices of the dominating set. If an (unguarded) vertex is attacked, at least one guard can then react by moving there. This yields a new set of guards, which may not be dominating anymore. A dominating set is eternal if one can endlessly resist to attacks. From the attacker's perspective, if we are given a non-eternal dominating set, the question is to determine how fast can we provoke an attack that cannot be handled by a neighboring guard. We investigate this question from a computational complexity point of view, by showing that this question is PSPACE-hard, even for graph classes where finding a minimum eternal dominating set is in P. We then complement this result by giving polynomial time algorithms for cographs and trees, and showing a connection with treedepth for the latter. We also investigate the problem from a parameterized complexity perspective, mainly considering two parameters: the number of guards and the number of steps.

关键词： eternal dominating set treedepth PSPACE-completeness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds

引用

Proceedings of the ACM on Management of Data 2025年第1期3卷 1-25页

作者： Aaron Huber Oliver Kennedy Atri Rudra Zhuoyue Zhao Su Feng Boris Glavic University at Buffalo Buffalo USA Nanjing Tech University Nanjing China University of Illinois Chicago Illinois USA

Probabilistic databases (PDBs) provide users with a principled way to query data that is incomplete or imprecise. In this work, we study computing expected multiplicities of query results over probabilistic databases under bag semantics which has PTIME data complexity. However, does this imply that bag probabilistic databases are practical? We strive to answer this question from both a theoretical as well as a systems perspective. We employ concepts from fine-grained complexity to demonstrate that exact bag probabilistic query processing is fundamentally less efficient than deterministic bag query evaluation, but that fast approximations are possible by sampling monomials from a circuit representation of a result tuple's lineage. A remaining issue, however, is that constructing such circuits, while in PTIME, can nonetheless have significant overhead. To avoid this cost, we utilize approximate query processing techniques to directly sample monomials without materializing lineage upfront. Our implementation in FastPDB provides accurate anytime approximation of probabilistic query answers and scales to datasets orders of magnitude larger than competing methods.

关键词： approximate query processing fine-grained complexity lineage polynomials parameterized complexity probabilistic data model

来源：评论

学校读者我要写书评

暂无评论

Kernel for Proper Helly Circular-Arc Vertex Deletion: Smaller and Simpler via Graph Isomorphism 17th

Kernel for Proper Helly Circular-Arc Vertex Deletion: Small...

引用

17th International Conference on Combinatorial Optimization and Applications, COCOA 2024

作者： Yuan, Hanchun Zhang, Zhen School of Computer Science and Technology Zhejiang Normal University Jinhua 321004 China School of Advanced Interdisciplinary Studies Hunan University of Technology and Business Changsha 410205 China

ISBN: (纸本)9789819644445

The modification problems toward subclasses of claw-free graphs have been investigated a lot in recent years. Proper Helly circular-arc graph is an important subclass of claw-free graphs. In this paper, we give an O(k⁸) vertex-kernel for proper Helly circular-arc vertex deletion, which is much better than the O(k⁸⁸) vertex-kernel [LATIN 24]. Our kernelization is based on small graph enumeration and isomorphism, which may be helpful for other graph classes with large forbidden induced subgraphs. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： claw-free kernelization parameterized complexity proper Helly circular-arc graph vertex deletion

来源：评论

学校读者我要写书评

暂无评论

An FPT algorithm for timeline cover

引用

Journal of Computer and System Sciences 2025年 154卷

作者： Riccardo Dondi Manuel Lafond Dipartimento di Lettere Filosofia Comunicazione Università degli Studi di Bergamo Bergamo Italy Department of Computer Science Université de Sherbrooke Street Sherbrooke Canada

One of the most studied problem in theoretical computer science, Vertex Cover , has been recently considered in the temporal graph framework. Here we study a Vertex Cover variant, called k- TimelineCover . Given a temporal graph k- TimelineCover asks to define an interval for each vertex so that for every temporal edge existing in a timestamp t , at least one of the endpoints has an interval that includes t . The goal is to decide whether it is possible to cover every temporal edge while using vertex intervals of total span at most k . k- TimelineCover has been shown to be NP-hard, but its parameterized complexity has not been fully understood when parameterizing by the span of the solution. We settle this open problem by giving an FPT algorithm that combines two techniques, a modified form of iterative compression and a reduction to Digraph Pair Cut .

关键词： Temporal graphs Temporal vertex cover Graph algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Possible winner problems on partial tournaments: a parameterized study

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第3期33卷 882-896页

作者： Yang, Yongjie Guo, Jiong Univ Saarland Saarbrucken Germany Shandong Univ Sch Comp Sci & Technol Jinan Peoples R China

We study possible winner problems related to the uncovered set and the Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study a problem where given a partial tournament D and a subset X of vertices, we are asked to add some arcs to D such that all vertices in X are included in the uncovered set. We focus on two parameterizations: parameterized by |X| and parameterized by the number of arcs to be added. In addition, we study a parameterized variant of the problem which is to determine whether all vertices of X can be included in the uncovered set by reversing at most k arcs. Finally, we study some parameterizations of a possible winner problem on partial tournaments, where we are given a partial tournament D and a distinguished vertex p, and asked whether D has a maximal transitive subtournament with p being the 0-indegree vertex. These parameterized problems are related to the Banks set. We achieve results, -hardness results as well as results along with a kernelization lower bound for the problems studied in this paper.

关键词： Tournament solution Banks set Uncovered set parameterized complexity Fixed-parameter tractable

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：