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

作者： Suchý, Ondřej Charles University of Prague

Title: parameterized complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisors e-mail address: honza@*** Abstract: This thesis deals with the parameterized complexity of NP-hard graph problems. We explore the complexity of the problems in various scenarios, with respect to miscellaneous parameters and their combina- tions. Our aim is rather to classify in this multivariate manner whether the particular parameters make the problem fixed-parameter tractable or intractable than to present the algorithm achieving the best running time. In the questions we study typically the first-choice parameter is unsuccessful, in which case we propose to use less standard ones. The first family of problems investigated provides a common general- ization of many well known and studied domination and independence problems. Here we suggest using the dual parameterization and show that, in contrast to the standard solution-size, it can confine the in- evitable combinatorial explosion. Further studied problems are ana- logues of the Steiner problem in directed graphs. Here the parameter- ization by the number of terminals to be connected seems to be previ- ously unexplored in the directed setting. Unfortunately, the problems are shown to be...

关键词： parameterized complexity graph Steiner problem generalized domination equitable partitions

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with fixed energy recharging times to minimize the number of late jobs and the number of just-in-time jobs: A parameterized complexity analysis

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2025年第1期324卷 40-48页

作者： Yu, Renjie Oron, Daniel Univ Sydney Business Sch Darlington NSW 2006 Australia

We study single-machine scheduling problems where processing each job requires both processing time and rechargeable energy. Subject to a predefined energy capacity, energy can be recharged after each job during a fixed recharging period. Our focus is on two due date-related scheduling criteria: minimizing the number of late jobs and maximizing the weighted number of jobs completed exactly at their due dates. This study aims to analyze the parameterized tractability of the two problems and develop fixed-parameter algorithms. with respect to three natural parameters the number of different due dates, the number of different processing times, and the number of different energy consumptions. Following the proofs of NP-hardness across several contexts, we demonstrate that both problems remain intractable when parameterized by and . To complement our results, we show that both problems become fixed-parameter tractable (FPT) when parameterized by u, and, and are solvable in polynomial time when both, Ve and, vp are constant.

关键词： Single machine parameterized complexity FPT XP W[t]

来源：评论

学校读者我要写书评

暂无评论

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 coloring problems: Treewidth versus vertex cover

引用

THEORETICAL COMPUTER SCIENCE 2011年第23期412卷 2513-2523页

作者： Fiala, Jiri Golovach, Petr A. Kratochvil, Jan Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci ITI Prague Czech Republic Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

We compare the fixed parameter complexity of various variants of coloring problems (including LIST COLORING, PRECOLORING EXTENSION, EQUITABLE COLORING, L(p, 1)-LABELING and CHANNEL ASSIGNMENT) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Graph colorings Graph labelings parameterized complexity Vertex cover

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Asynchronous Border Minimization

引用

ALGORITHMICA 2019年第1期81卷 201-223页

作者： Ganian, Robert Kronegger, Martin Pfandler, Andreas Popa, Alexandru Johannes Kepler Univ Linz Linz Austria TU Wien Vienna Austria Univ Bucharest Bucharest Romania Univ Siegen Siegen Germany Natl Inst Res & Dev Informat Bucharest Romania

Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). The common task of these two problems is to create so-called probe sequences (essentially a string) in a microarray. Here, the goal of the former problem is to determine an assignment of each probe sequence to a unique cell of the array and afterwards to construct the sequences at their respective cells while minimizing the border length of the probes. In contrast, for the latter problem the assignment of the probes to the cells is already given. In this paper we investigate the parameterized complexity of the natural exhaustive variants of BMP and P-BMP, termed BMPe and P-BMPe respectively, under several natural parameters. We show that BMPe and P-BMPe are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input () and the number of rows of the microarray (r);and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMPe is in FPT when parameterized by c and . We complement our tractability results with a number of corresponding hardness results.

关键词： parameterized complexity Fixed-parameter tractability NP-hard problem Microarrays

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Small Weight Automorphisms and Isomorphisms

引用

ALGORITHMICA 2021年第12期83卷 3567-3601页

作者： Arvind, V Koebler, Johannes Kuhnert, Sebastian Toran, Jacobo Inst Math Sci HBNI Chennai Tamil Nadu India Humboldt Univ Inst Informat Berlin Germany Univ Ulm Inst Theoret Informat Ulm Germany

We study the parameterized complexity of computing nontrivial automorphisms of weight k for a given hypergraph X = (V, E), with k as fixed parameter, where the weight of a permutation pi is an element of S-n is the number of points moved by pi. Building on the earlier work of Schweitzer (in: Proceedings of 19th ESA, Springer, Berlin, 2011. https://***/10.1007/978-3-642-23719-5_32), we show the following results: (1) Computing nontrivial automorphisms of weight at most k for d-hypergraphs (that is, with edge-size bounded by d) remains fixed parameter tractable, with d treated as a second fixed parameter. Likewise, finding isomorphisms of weight k between d-hypergraphs X and Y (both defined on vertex set [n]) remains fixed parameter tractable. (2) For dealing with the exact weight k version of the problem, we introduce a more general algorithmic problem PERMCODE: given a permutation group G by a generating set and a fixed parameter k, is there is a nontrivial element of G with support at most (or exactly) k? We give a method for shrinking large orbits of the given group G to obtain subgroups while maintaining existence of weight at most k elements in it. An application of this yields an FPT algorithm for finding exact weight k nontrivial automorphisms in d-hypergraphs, d as second fixed parameter. (3) For hypergraphs with edges of unbounded size, we show that the problem is in FPTGI. (4) Computing d-hypergraph isomorphisms of weight exactly k is fixed parameter tractable. This requires a more complicated orbit shrinking technique.

关键词： parameterized complexity Graph automorphism Graph isomorphism

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Conflict-Free Set Cover

引用

THEORY OF COMPUTING SYSTEMS 2021年第3期65卷 515-540页

作者： Jacob, Ashwin Majumdar, Diptapriyo Raman, Venkatesh HBNI Inst Math Sci Chennai Tamil Nadu India Royal Holloway Univ London Egham Surrey England

SET COVER is one of the well-known classical NP-hard problems. We study the conflict-free version of the SET COVER problem. Here we have a universe U, a family F of subsets of U and a graph G(F) on the vertex set F and we look for a subfamily F' subset of F of minimum size that covers U and also forms an independent set in G(F). We study conflict-free SET COVER in parameterized complexity by restricting the focus to the variants where SET COVER is fixed parameter tractable (FPT). We give upper bounds and lower bounds for the running time of conflict-free version of SET COVER with and without duplicate sets along with restrictions to the graph classes of G(F). For example, when pairs of sets in F intersect in at most one element, for a solution of size k, we give an f (k)vertical bar F vertical bar(o(k)) lower bound for any computable function f assuming ETH even if G(F) is bipartite, but an O*(3(k2)) FPT algorithm (O* notation ignores polynomial factors of input) when G(F) is chordal.

关键词： parameterized complexity Set cover Fixed parameter tractability W-Hardness

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第4期22卷 684-698页

作者： Liu, Chunmei Song, Yinglei Howard Univ Dept Syst & Comp Sci Washington DC 20059 USA Univ Maryland Eastern Shore Dept Math & Comp Sci Princess Anne MD 21853 USA

In this paper, we study the parameterized complexity of DOMINATING SET problem in chordal graphs and near chordal graphs. We show the problem is W[2]hard and cannot be solved in time n(o(k)) in chordal and s-chordal (s > 3) graphs unless W[1] = FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP = P, the minimum dominating set in a chordal or s-chordal (s > 3) graph cannot be approximated within a ratio of c/3 ln n in polynomial time, where n is the number of vertices in the graph and 0 < c < 1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the INDEPENDENT DOMINATING SET problem and the CONNECTED DOMINATING SET problem in chordal or near chordal graphs.

关键词： Chordal graphs Dominating set Independent dominating set parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of completeness reasoning for conjunctive queries

引用

THEORETICAL COMPUTER SCIENCE 2021年 864卷 34-49页

作者： Liu, Xianmin Li, Jianzhong Li, Yingshu Feng, Yuqiang Harbin Inst Technol Harbin 150001 Heilongjiang Peoples R China Georgia State Univ Atlanta GA 30303 USA

Incompleteness management has become a popular research topic and been viewed in many applications in the area of data quality and data management. Traditional methods for handling incompleteness assume data is totally complete or incomplete. However, in practical applications, data is often partial complete, which means that data is not totally complete but some special parts of the data satisfying given semantic specifications are complete. Intuitively, partial complete data can still give complete answers for queries consistent with the semantic specifications. Therefore, it is highly needed to study the fundamental problems for managing partial complete data. However, as far as known by us, there are only few works focusing on this area. The most important and fundamental problem, completeness reasoning, is studied from the aspect of parameterized complexity by this paper. The completeness reasoning problem, TC-QC (Table Completeness to Query Completeness), is first formally defined and studied by Razniewski et al. [1]. Given completeness statements of data, the goal of the TC-QC problem is to determine whether the result of a special query Q is complete, that is to reason query completeness based on given data completeness. Razniewski et al. have shown that the TC-QC problem is NP-hard even for conjunctive queries, and a natural and interesting question is whether or not TC-QC can be solved efficiently by parameterized algorithms. To answer that, the parameterized complexities of completeness reasoning for conjunctive queries are studied by the paper. First, it is shown that, considering the parameterizations defined by the size of query completeness or table completeness, the parameterized TC-QC problem for conjunctive queries is para-NP-complete, which strongly indicate that the TC-QC problems parameterized by the above two parameters do not admit fixed-parameter tractable algorithms. Then, for more special cases parameterized by different constraints on quer

关键词： Completeness reasoning parameterized complexity Conjunctive queries

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：