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

parameterized complexity of finding connected induced subgraphs

THEORETICAL COMPUTER SCIENCE 2015年第Part1期607卷 49-59页

作者： Cai, Leizhen Ye, Junjie Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

For a graph property Pi, i.e., a family Pi of graphs, the CONNECTED INDUCED Pi-SUBGRAPH problem asks whether an input graph G contains k vertices V' such that the induced subgraph G[V'] is connected and satisfies property Pi. In this paper, we study the parameterized complexity of CONNECTED INDUCED Pi-SUBGRAPH for decidable hereditary properties Pi, and give a nearly complete characterization in terms of whether Pi includes all complete graphs, all stars, and all paths. As a consequence, we obtain a complete characterization of the parameterized complexity of our problem when Pi is the family of H-free graphs for a fixed graph H with h >= 3 vertices: W[1]-hard if H is K-h, (K-h) over bar, or K-1,K-h-1;and FPT otherwise. Furthermore, we also settle the parameterized complexity of the problem for many well-known families Pi of graphs: FPT for perfect graphs, chordal graphs, and interval graphs, but W[1]-hard for forests, bipartite graphs, planar graphs, line graphs, and degree-bounded graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Hereditary properties Connected induced subgraphs

来源：评论

学校读者我要写书评

暂无评论

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 Dichotomy for (r, a)-Vertex Deletion

引用

THEORY OF COMPUTING SYSTEMS 2017年第3期61卷 777-794页

作者： Baste, Julien Faria, Luerbio Klein, Sulamita Sau, Ignasi LIRMM CNRS AlGCo Project Team Montpellier France Univ Estado Rio de Janeiro FFP Rio De Janeiro Brazil Univ Fed Rio de Janeiro Rio De Janeiro Brazil

For two integers r, a"" 0, a graph G = (V, E) is an (r, a"")-graph if V can be partitioned into r independent sets and a"" cliques. In the parameterized (r, a"")-Vertex Deletion... 详细信息

For two integers r, a"" 0, a graph G = (V, E) is an (r, a"")-graph if V can be partitioned into r independent sets and a"" cliques. In the parameterized (r, a"")-Vertex Deletion problem, given a graph G and an integer k, one has to decide whether at most k vertices can be removed from G to obtain an (r, a"")-graph. This problem is NP-hard if r + a"" 1 and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of (r, a"")-Vertex Deletion was known for all values of (r, a"") except for (2,1), (1,2), and (2,2). We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of k. We consider as well the version of (r, a"")-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem.

关键词： Graph modification problem parameterized complexity Iterative compression FPT-algorithm Single-exponential algorithm

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of finding a spanning tree with minimum reload cost diameter

引用

NETWORKS 2020年第3期75卷 259-277页

作者： Baste, Julien Gozupek, Didem Paul, Christophe Sau, Ignasi Shalom, Mordechai Thilikos, Dimitrios M. Univ Montpellier LIRMM Montpellier France Gebze Tech Univ Dept Comp Engn Kocaeli Turkey Univ Montpellier LIRMM CNRS Montpellier France TelHai Coll Qiryat Shemona Israel Bogazici Univ Dept Ind Engn Istanbul Turkey Natl & Kapodistrian Univ Athens Dept Math Athens Greece

We study the minimum diameter spanning tree problem under the reload cost model (Diameter-Tree for short) introduced by Wirth and Steffan. In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the Diameter-Tree problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that Diameter-Tree is para-NP-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove Diameter-Tree to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan proved that the problem can be solved in polynomial time on graphs with Delta = 3, and Galbiati proved that it is NP-hard if Delta = 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta = 3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that Diameter-Tree is in XP and W[1]-hard parameterized by the treewidth plus Delta.

关键词： dynamic programming FPT algorithm minimum diameter spanning tree parameterized complexity reload cost problems treewidth

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of satisfactory partition problem

引用

THEORETICAL COMPUTER SCIENCE 2022年 907卷 113-127页

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

Given an undirected graph G, we study the SATISFACTORY PARTITION problem, where the goal is to decide whether it is possible to partition the vertex set of G into two parts such that each vertex has at least as many neighbours in its own part as in the other part. The BALANCED SATISFACTORY PARTITION problem is a variant of the above problem where the two partite sets are required to have the same cardinality. Both problems are known to be NP-complete. This problem was introduced by Gerber and Kobler (2000) [9] and further studied by other authors, 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) SATISFACTORY PARTITION is polynomial-time solvable for block graphs, (2) SATISFACTORY PARTITION and BALANCED SATISFACTORY PARTITION are fixed parameter tractable (FPT) when parameterized by neighbourhood diversity. (3) SATISFACTORY PARTITION and its balanced version can be solved in polynomial time for graphs of bounded clique-width, and (4) BALANCED SATISFACTORY PARTITION is W[1]-hard when parameterized by treewidth. (C) 2022 Elsevier B.V. All rights reserved.

关键词： parameterized complexity FPT W-hard Treewidth Clique-width Neighbourhood diversity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Superstring Problems

引用

ALGORITHMICA 2017年第3期79卷 798-813页

作者： Bliznets, Ivan Fomin, Fedor V. Golovach, Petr A. Karpov, Nikolay Kulikov, Alexander S. Saurabh, Saket Russian Acad Sci St Petersburg Dept Steklov Inst Math St Petersburg Russia Univ Bergen Dept Informat Bergen Norway Inst Math Sci Madras Tamil Nadu India

In the Shortest Superstring problem we are given a set of strings and S = {s(1),..., s(n}) integer l and the question is to decide whether there is a superstring s of length at most l containing all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time 2(O(k)) poly(n) finds a superstring of length at most l containing at least k strings of S. We complement this by a lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about "below guaranteed values" parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization "below matching" is hard.

关键词： Shortest superstring parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity and approximation algorithms

引用

COMPUTER JOURNAL 2008年第1期51卷 60-78页

作者： Marx, Daniel Humboldt Univ Inst Informat D-10099 Berlin Germany

Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type and propose directions for future research.

关键词： approximation algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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 and approximation issues for the colorful components problems

引用

THEORETICAL COMPUTER SCIENCE 2018年 739卷 1-12页

作者： Dondi, Riccardo Sikora, Florian Univ Bergamo Dipartimento Sci Umane & Sociali Bergamo Italy Univ Paris 09 PSL Res Univ CNRS UMR 7243 LAMSADE F-75016 Paris France

The quest for colorful components (connected components where each color is associated with at most one vertex) inside a vertex-colored graph has been widely considered in the last ten years. Here we consider two variants, Minimum Colorful Components (MCC) and Maximum Edges in transitive Closure (MEC), introduced in 2011 in the context of orthology gene identification in bioinformatics. The input of both MCC and MEC is a vertex-colored graph. MCC asks for the removal of a subset of edges, so that the resulting graph is partitioned in the minimum number of colorful connected components;MEC asks for the removal of a subset of edges, so that the resulting graph is partitioned in colorful connected components and the number of edges in the transitive closure of such a graph is maximized. We study the parameterized and approximation complexity of MCC and MEC, for general and restricted instances. For MCC on trees we show that the problem is basically equivalent to Minimum Cut on Trees, thus MCC is not approximable within factor 1.36 - epsilon, it is fixed-parameter tractable and it admits a poly-kernel (when the parameter is the number of colorful components). Moreover, we show that MCC, while it is polynomial time solvable on paths, it is NP-hard even for graphs with constant distance to disjoint paths number. Then we consider the parameterized complexity of MEC when parameterized by the number k of edges in the transitive closure of a solution (the graph obtained by removing edges so that it is partitioned in colorful connected components). We give a fixed-parameter algorithm for MEC parameterized by k and, when the input graph is a tree, we give a poly-kernel. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Colorful components parameterized complexity Algorithms Computational biology

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity classes beyond para-NP

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 87卷 16-57页

作者： de Haan, Ronald Szeider, Stefan TU Wien Algorithms & Complex Grp Vienna Austria

Today's propositional satisfiability (SAT) solvers are extremely powerful and can be used as an efficient back-end for solving NP-complete problems. However, many fundamental problems in logic, in knowledge representation and reasoning, and in artificial intelligence are located at the second level of the Polynomial Hierarchy or even higher, and hence for these problems polynomial-time transformations to SAT are not possible, unless the hierarchy collapses. Recent research shows that in certain cases one can break through these complexity barriers by fixed-parameter tractable (fpt) reductions to SAT which exploit structural aspects of problem instances in terms of problem parameters. These reductions are more powerful because their running times can grow superpolynomially in the problem parameters. In this paper we develop a general theoretical framework that supports the classification of parameterized problems on whether they admit such an fpt-reduction to SAT or not. (C) 2017 The Author(s). Published by Elsevier Inc.

关键词： parameterized complexity Fpt-reductions Polynomial hierarchy Weft-hierarchy

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：