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

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

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for variants of 3-Hitting Set

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第4期49卷 1-14页

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the A-Multi3-Hitting Set problem (A-M3HS), where A subset of{1,2,3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \subseteq \{1,2,3\}$$\end{document}, the input is a hypergraph G in which the hyperedges have sizes at most 3 and an integer k, and the goal is to decide if there is a set S of at most k vertices such that |S boolean AND e|is an element of A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|S \cap e| \in A$$\end{document} for every hyperedge e. In this paper we give O & lowast;(2.027k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O<^>*(2.027<^>k)$$\end{document}-time algorithms for {1}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1\}$$\end{document}-M3HS and {1,3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,3\}$$\end{document}-M3HS, and an O & lowast;(1.381k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O<^>*(1.381<^>k)$$\end{document}-time algorithm for {2}\docume

关键词： Graph algorithms parameterized complexity Branching algorithms

来源：评论

学校读者我要写书评

暂无评论

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 Jinhua321004 China School of Advanced Interdisciplinary Studies Hunan University of Technology and Business Changsha410205 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(k8) vertex-kernel for proper Helly circular-arc vertex deletion, which is much better than the O(k88) 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Finding disjoint paths on edge-colored graphs: more tractability results

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第4期36卷 1315-1332页

作者： Dondi, Riccardo Sikora, Florian Univ Bergamo Dipartimento Lettere & Comunicaz Bergamo Italy Univ Paris 09 PSL Res Univ CNRS LAMSADE Paris France

The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (called MaxCDP) has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate how the complexity of the problem depends on graph parameters (namely the number of vertices to remove to make the graph a collection of disjoint paths and the size of the vertex cover of the graph), which makes sense since graphs in social networks are not random and have structure. The problem was known to be hard to approximate in polynomial time and not fixed-parameter tractable (FPT) for the natural parameter. Here, we show that it is still hard to approximate, even in FPT-time. Finally, we introduce a new variant of the problem, called MaxCDDP, whose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDP is already hard on graphs at distance two from disjoint paths.

关键词： parameterized complexity Approximation Social networks Edge-colored graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：