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

parameterized complexity of dominating set variants in almost cluster and split graphs

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 150卷

作者： Goyal, Dishant Jacob, Ashwin Kumar, Kaushtubh Majumdar, Diptapriyo Raman, Venkatesh Indian Inst Technol Delhi New Delhi India Natl Inst Technol Calicut Calicut India Mentor G Corp Noida India Indraprastha Inst Informat Technol Delhi New Delhi India HBNI Inst Math Sci Chennai India

We consider structural parameterizations of several variants of DOMINATING SET in the parameter ecology program. We give improved FPT algorithms and lower bounds under well-known conjectures for DOMINATING SET and its variants in graphs that are k vertices away from a cluster graph or a split graph. These are graphs in which there is a set of k vertices (called the modulator) whose deletion results in a cluster graph or a split graph. We also call k as the deletion distance (to the appropriate class of graphs). For example, we show that when parameterized by the deletion distance k to cluster graphs: DOMINATING SET, INDEPENDENT DOMINATING SET, DOMINATING CLIQUE, EFFICIENT DOMINATING SET and TOTAL DOMINATING SET can be solved in 3knO(1)-time. Additionally, when parameterized by the deletion distance k to split graphs, we prove that EFFICIENT DOMINATING SET can be solved in 3k/2nO(1)-time breaking the 2k barrier. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： parameterized complexity Domination problems Structural parameterization Set cover with partition Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of weighted team definability

引用

MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE 2024年第5期34卷 375-389页

作者： Kontinen, Juha Mahmood, Yasir Meier, Arne Vollmer, Heribert Univ Helsinki Dept Math & Stat Helsinki Finland Paderborn Univ Dept Comp Sci Paderborn Germany Leibniz Univ Hannover Inst Theoret Informat Hannover Germany

In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analog of one of the most studied problems in parameterized complexity, the notion of weighted Fagin-definability, which is formulated in terms of satisfaction of first-order formulas with free relation variables. We focus on the parameterized complexity of weighted team definability for a fixed formula $\varphi$ of central team-based logics. Given a first-order structure $\mathcal{A}$ and the parameter value $k\in \mathbb N$ as input, the question is to determine whether $\mathcal{A},T\models \varphi$ for some team T of size k. We show several results on the complexity of this problem for dependence, independence, and inclusion logic formulas. Moreover, we also relate the complexity of weighted team definability to the complexity classes in the well-known W-hierarchy as well as paraNP.

关键词： parameterized complexity descriptive complexity weighted definability team semantics dependence logic independence logic inclusion logic

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity OF UNTANGLING KNOTS\ast

引用

SIAM JOURNAL ON COMPUTING 2024年第2期53卷 431-479页

作者： Legrand-Duchesne, Clement Rai, Ashutosh Tancer, Martin Univ Bordeaux CNRS INP LaBRIUMR 5800Bordeaux F-33400 Talence France IIT Delhi Dept Math Hauz Khas New Delhi 110016 India Charles Univ Prague Fac Math & Phys Dept Appl Math Malostranske nam 25 Prague 1 Czech Republic

Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP -complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called defect. Roughly speaking, it measures the efficiency of the moves used in the shortest untangling sequence of Reidemeister moves. We show that in a shortest untangling sequence the II - moves, that is, the moves removing two adjacent crossings, can be essentially performed greedily. Using that, we show that this problem belongs to W[P] when parameterized by the defect. We also show that this problem is W[P]-hard by a reduction from MINIMUM AXIOM SET.

关键词： unknot recognition parameterized complexity Reidemeister moves W[P]-complete

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity for iterated type partitions and modular-width

引用

DISCRETE APPLIED MATHEMATICS 2024年 350卷 100-122页

作者： Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. Univ Campania L Vanvitelli Dept Psychol Caserta Italy Univ Salerno Dept Comp Sci Fisciano Italy

This paper deals with the complexity of some natural graph problems parameterized by some measures that are restrictions of clique-width, such as modular-width and neighborhood diversity. We introduce a novel parameter, called iterated type partition number, that can be computed in linear time and nicely places between modular-width and neighborhood diversity. We prove that the EQUITABLE COLORING problem is W [ 1 ] - hard when parameterized by the iterated type partition number. This result extends to modular-width, answering an open question on the complexity of EQUITABLE COLORING when parameterized by modular-width. On the contrary, we show that the EQUITABLE COLORING problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition number, which enables us to find optimal solutions for several graph problems. As an example, in this paper, we present algorithms parameterized by the iterated type partition number of the input graph for some generalized versions of the MAXIMUM CLIQUE, MINIMUM GRAPH COLORING, (TOTAL) MINIMUM DOMINATING SET, MINIMUM VERTEX COVER and MAXIMUM INDEPENDENT SET problems. Each algorithm outputs not only the optimal value but also the optimal solution. We stress that while the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. We finally show that the proposed scheme can be used to devise polynomial kernels, with respect to iterated type partition number, for the decisional version of most of the problems mentioned above. (c) 2024 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Neighborhood diversity Modular-width Fixed-parameter tractability Kernelization algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Reconfiguration of Atoms

引用

ALGORITHMICA 2024年第10期86卷 3284-3308页

作者： Cooper, Alexandre Maaz, Stephanie Mouawad, Amer E. Nishimura, Naomi Univ Waterloo Inst Quantum Comp Waterloo ON Canada Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON Canada Amer Univ Beirut Dept Comp Sci Beirut Lebanon

Our work is motivated by the challenges presented in preparing arrays of atoms for use in quantum simulation. The recently-developed process of loading atoms into traps results in approximately half of the traps being filled. To consolidate the atoms so that they form a dense and regular arrangement, such as all locations in a grid, atoms are rearranged using moving optical tweezers. Time is of the essence, as the longer that the process takes and the more that atoms are moved, the higher the chance that atoms will be lost in the process. Viewed as a problem on graphs, we wish to solve the problem of reconfiguring one arrangement of tokens (representing atoms) to another using as few moves as possible. Because the problem is NP-complete on general graphs as well as on grids, we focus on the parameterized complexity for various parameters, considering both undirected and directed graphs, and tokens with and without labels. For unlabelled tokens, the problem is fixed-parameter tractable when parameterized by the number of tokens, the number of moves, or the number of moves plus the number of vertices without tokens in either the source or target configuration, but intractable when parameterized by the difference between the number of moves and the number of differences in the placement of tokens in the source and target configurations. When labels are added to tokens, however, most of the tractability results are replaced by hardness results.

关键词： Combinatorial reconfiguration parameterized complexity Quantum simulation

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of broadcasting in graphs

引用

THEORETICAL COMPUTER SCIENCE 2024年 997卷

作者： Fomin, Fedor V. Fraigniaud, Pierre Golovach, Petr A. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Paris Cite Inst Rech Informat Fondamentale 8 Pl Aurelie Nemours F-75013 Paris France CNRS 8 Pl Aurelie Nemours F-75013 Paris France

The task of the broadcast problem is, given a graph G and a source vertex s , to compute the minimum number of rounds required to disseminate a piece of information from s to all vertices in the graph. It is assumed that, at each round, an informed vertex can transmit the information to at most one of its neighbors. The broadcast problem is known to NP -hard. We show that the problem is FPT when parametrized by the size k of a feedback edge set, or by the size k of a vertex cover, or by k = n - t , where t is the input deadline for the broadcast protocol to complete.

关键词： Broadcasting Telephone model parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity Classes Defined by Threshold Circuits and Their Connection with Sorting Networks

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2024年第6期35卷 651-668页

作者： Paranhos, Raffael Muralha Silva, Janio Carlos Nascimento Souza, Ueverton dos Santos Univ Fed Fluminense Niteroi Inst Computacao Rio De Janeiro Brazil Inst Fed Tocantins Campus Porto Nacl Porto Nacl Tocantins Brazil

The main complexity classes of the parameterized Intractability Theory are based on weighted Boolean circuit satisfiability problems and organized into a hierarchy so-called W-hierarchy. The W-hierarchy enables fine-grained complexity analyses of parameterized problems that are unlikely to belong to the FPT class. In this paper, we introduce the Th-hierarchy, a natural generalization of the W-hierarchy defined by unweighted threshold circuit satisfiability problems. Investigating the relationship between Th-hierarchy and W-hierarchy, we discuss the complexity of transforming Threshold circuits into Boolean circuits, and observe that sorting networks are powerful tools to handle such transformations. First, we show that these hierarchies collapse at the last level (W[P] =Th[P]). After that, we present a time complexity analysis of an AKS sorting network construction, which supports some of our results. Finally, we prove that Th[t] subset of W[SAT] for every t is an element of N. As a by-product, our studies suggest that it is relevant to consider a new class based on logarithmic depth circuits in the W-hierarchy.

关键词： Threshold circuits AKS network parameterized complexity W-hierarchy

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of locally minimal defensive alliances

引用

DISCRETE APPLIED MATHEMATICS 2025年 372卷 324-340页

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

A set S of vertices of a graph is a defensive alliance if, for each element of S, the majority of its neighbours is in S. We consider the notion of local minimality in this paper. We are interested in locally minimal defensive alliance of maximum size. This problem is known to be NP-hard 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) LOCALLY MINIMAL DEFENSIVE ALLIANCE is NP-complete, even when restricted to planar graphs, (2) a randomized FPT algorithm for EXACT CONNECTED LOCALLY MINIMAL DEFENSIVE ALLIANCE parameterized by solution size, (3) LOCALLY MINIMAL DEFENSIVE ALLIANCE is fixed-parameter tractable (FPT) when parameterized by neighbourhood diversity, (4) LOCALLY MINIMAL DEFENSIVE ALLIANCE parameterized by treewidth is W[1]-hard and thus not FPT (unless FPT = W[1]), (5) LOCALLY MINIMAL DEFENSIVE ALLIANCE can be solved in polynomial time for graphs of bounded treewidth. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

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

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Logic-based Argumentation in Schaefer's Framework

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2023年第3期24卷 1-25页

作者： Mahmood, Yasir Meier, Arne Schmidt, Johannes Leibniz Univ Hannover Inst Theoret Informat Appelstr 9A D-30167 Hannover Germany Jonkoping Univ Sch Engn Dept Comp Sci & Informat Gjuterigatan 5 S-55111 Jonkoping Sweden

Argumentation is a well-established formalism dealing with conflicting information by generating and comparing arguments. It has been playing a major role in AI for decades. In logic-based argumentation, we explore the internal structure of an argument. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this article, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Creignou et al. 2014 and Parson et al., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: First, we consider all possible propositional fragments of the problem within Schaefer's framework (STOC 1978) and then study different parameterizations for each of the fragments. We identify a list of reasonable structural parameters (size of the claim, support, knowledge base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (para-NP and beyond).

关键词： parameterized complexity logic-based argumentation Schaefer's framework

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Dynamic Belief Updates: A Complete Map

引用

JOURNAL OF LOGIC AND COMPUTATION 2023年第6期33卷 1270-1300页

作者： Bolander, Thomas Lequen, Arnaud Tech Univ Denmark Dept Appl Math & Comp Sci DK-2800 Lyngby Denmark Ecole Normale Super Rennes Dept Comp Sci F-35170 Bruz France

Dynamic Belief Update is a model checking problem in Dynamic Epistemic Logic concerning the effect of applying a number of epistemic actions on an initial epistemic model. It can also be considered as a plan verification problem in epistemic planning. The problem is known to be PSPACE-hard. To better understand the source of complexity of the problem, previous research has investigated the complexity of 128 parameterized versions of the problem with parameters such as number of agents and size of epistemic actions. The complexity of many parameter combinations has been determined, but previous research left 14 parameter combinations open. In this paper, we solve all of these open problems. Most of the parameter combinations turns out to be fixed-parameter intractable, except for 2 that are fixed-parameter tractable.

关键词： parameterized complexity model checking dynamic epistemic logic plan verification

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：