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

Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2014年第7期80卷 1430-1447页

作者： Fomin, Fedor V. Kratsch, Stefan Pilipczuk, Marcin Pilipczuk, Michal Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway Tech Univ Berlin Berlin Germany Univ Warsaw Inst Informat PL-00325 Warsaw Poland

In the CLUSTER EDITING problem, also known as CORRELATION CLUSTERING, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, i.e. by adding/deleting at most k edges. We give a subexponential-time parameterized algorithm that in time 2(O(root pk)) + n(O(1)) decides whether G can be transformed into a cluster graph with exactly p cliques by changing at most k adjacencies. Our algorithmic findings are complemented by the following tight lower bound on the asymptotic behavior of our algorithm. We show that unless ETH fails, for any constant 0 < sigma <= 1, there is p = Theta(k(sigma)) such that there is no algorithm deciding in time 2(o(root pk)) . n(O)(1) whether G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Cluster editing Correlation clustering parameterized complexity Subexponential-time algorithms Exponential-time hypothesis

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of clustering problems for incomplete data

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年第1期134卷 1-19页

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Univ London Royal Holloway London England TU Wien Vienna Austria DePaul Univ Chicago IL 60614 USA Univ Leeds Leeds England

We study fundamental clustering problems for incomplete data. Specifically, given a set of incomplete d-dimensional vectors (representing rows of a matrix), the goal is to complete the missing vector entries in a way that admits a partitioning of the vectors into at most k clusters with radius or diameter at most r. We give characterizations of the parameterized complexity of these problems with respect to the parameters k, r, and the minimum number of rows and columns needed to cover all the missing entries. We show that the considered problems are fixed-parameter tractable when parameterized by the three parameters combined, and that dropping any of the three parameters results in parameterized intractability. A byproduct of our results is that, for the complete data setting, all problems under consideration are fixed-parameter tractable parameterized by k + r. (c) 2022 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Clustering Incomplete data

来源：评论

学校读者我要写书评

暂无评论

Paths of bounded length and their cuts: parameterized complexity and algorithms

引用

DISCRETE OPTIMIZATION 2011年第1期8卷 72-86页

作者： Golovach, Petr A. Thilikos, Dimitrios M. Univ Athens Dept Math GR-15784 Athens Greece Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length I of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both k and I and hardness results when the parameter is only one of k and I. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Bounded length disjoint paths Bounded length cuts parameterized complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity and kernelization of resilience for database queries

引用

THEORETICAL COMPUTER SCIENCE 2020年 840卷 199-211页

作者： Miao, Dongjing Li, Jianzhong Cai, Zhipeng Harbin Inst Technol Sch Comp Sci & Technol Harbin 150000 Heilongjiang Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

Given a database instance and a query on it whose result is initially non-empty, the resilience decision problem is to decide if there exist a small enough number of facts in the database instance such that the deletion of these facts empties the result of the given query. In this paper, we revisit the resilience decision problem. We investigate the parameterized complexity for various classes of database queries. We consider the factors including the query size and the number of variables, and present several intractable cases even from the perspective of parameterized complexity. Meanwhile, we refine the characteristics of resilience for self-join-free conjunctive queries containing triads, and show that it is still NP-hard even if the structure of the input database instance is simple. This result implies the hardness essentially comes from the parity of triangle sequence instead of the complicate (non-planar) intersections of cycles. On the other hand, we also obtain some positive results showing that the resilience decision problem is still fixed parameter tractable for an important case through kernelization. Our work demonstrates a new insight for employing resilience computation in database operations. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Resilience Conjunctive query parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the Edge Monitoring problem

引用

INFORMATION PROCESSING LETTERS 2017年第May期121卷 39-44页

作者： Baste, Julien Beggas, Fairouz Kheddouci, Hamamache Sau, Ignasi CNRS LIRMM AIGCo Project Team Montpellier France Claude Bernard Lyon 1 Univ Univ Lyon LIRIS UMR5205 CNRS 43 Bd 11 Novembre 1918 F-69622 Villeurbanne France

In a graph G = (V, E), a vertex nu is an element of V monitors an edge {u, u'} is an element of E if {nu, u} is an element of E and {nu, u'} E E. Given an n-vertex graph G = (V, E), in which each edge is contained in at least one triangle, and an integer k, the EDGE MONITORING problem consists in finding a set S subset of V of size at most k such that each edge of the graph is monitored by at least one element of S. This problem is known to be NP-hard, even under the unit disk graph. We prove that it is also W[2]-hard when parameterized by k. Using Bidimensionality Theory, we provide an FPT algorithm running in time 2 (O(root ***(max)(e is an element of E) (omega(e))).n for the weighted version of EDGE MONITORING when the input graph is restricted to be apex-minor-free, in particular, it applies to planar graphs, and where we additionally impose each edge e to be monitored at least omega(e) times, and the solution to be contained in a set of selected vertices. (C) 2017 Elsevier B.V. All rights reserved.

关键词： EDGE MONITORING parameterized complexity FPT algorithm Bidimensionality Theory Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the geodesic hull number

引用

THEORETICAL COMPUTER SCIENCE 2019年 791卷 10-27页

作者： Kante, Mamadou Moustapha Marcilon, Thiago Sampaio, Rudini Univ Clermont Auvergne CNRS LIMOS Clermont Ferrand France Univ Fed Cariri Ctr Ciencias & Tecnol Juazeiro Do Norte Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil

Several recent papers obtained complexity results regarding the geodesic hull number hn(gd)(G) of a graph G. In this paper, we prove that determining whether hngd(G) <= k is W[2]-hard parameterized by k in diameter-two graphs and is W[1] -hard parameterized by tw +4, where tw is the treewidth of G. Despite this, for graphs with bounded treewidth tw, we prove that hngd(G) is computable in polynomial time O ((tw+2)(tw+5)n(2tw+5)). (C) 2019 Elsevier B.V. All rights reserved.

关键词： Geodesic convexity Hull number parameterized complexity Treewidth

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Equitable Coloring

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2019年第1期21卷 1页

作者： Gomes, Guilherme de C. M. Lima, Carlos V. G. C. dos Santos, Vinicius F. Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil

A graph on n vertices is equitably k-colorable if it is k-colorable and every color is used either [n/k] or [n/k] times. Such a problem appears to be considerably harder than vertex coloring, being NP-complete even for cographs and interval graphs. In this work, we prove that it is W[1]-hard for block graphs and for disjoint union of split graphs when parameterized by the number of colors;and W[1]-hard for K-1,K-4-free interval graphs when parameterized by treewidth, number of colors and maximum degree, generalizing a result by Fellows et al. (2014) through a much simpler reduction. Using a previous result due to Dominique de Werra (1985), we establish a dichotomy for the complexity of equitable coloring of chordal graphs based on the size of the largest induced star. Finally, we show that EQUITABLE COLORING is FPT when parameterized by the treewidth of the complement graph.

关键词： Equitable Coloring parameterized complexity Treewidth Chordal Graphs

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of perfectly matched sets *,**

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期958卷

作者： Agrawal, Akanksha Bhattacharjee, Sutanay Jana, Satyabrata Sahu, Abhishek Indian Inst Technol Madras Chennai India Homi Bhabha Natl Inst Natl Inst Sci Educ & Res OCC Bhubaneswar India HBNI Inst Math Sci Chennai India

For an undirected graph G, a pair of vertex disjoint subsets (A, B) is a pair of perfectly matched sets if each vertex in A (resp. B) has exactly one neighbor in B (resp. A). In the above, the size of the pair is |A| (= |B|). Given a graph G and a positive integer k, the PERFECTLY MATCHED SETS problem asks whether there exists a pair of perfectly matched sets of size at least k in G. This problem is known to be NP-hard on planar graphs and W[1]-hard on general graphs, when parameterized by k. However, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we study the problem parameterized by k, and design FPT algorithms for: i) apex-minor-free graphs running in time 2O( k) center dot nO(1), and ii) Kb,b-free graphs. We obtain a linear kernel for planar graphs and kO(d)-sized kernel for d-degenerate graphs. It is known that the problem is W[1]-hard on chordal graphs, in fact on split graphs, parameterized by k. We complement this hardness result by designing a polynomial-time algorithm for interval graphs.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Perfectly matched sets parameterized complexity Apex -minor -free graphs d -degenerate graphs Planar graphs Interval graphs

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Graph Modification to First-Order Logic Properties

引用

THEORY OF COMPUTING SYSTEMS 2020年第2期64卷 251-271页

作者： Fomin, Fedor V. Golovach, Petr A. Thilikos, Dimitrios M. Univ Bergen Dept Informat Bergen Norway Univ Montpellier AlGCo Project Team CNRS LIRMM Montpellier France

We establish connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order logic formula phi, we consider the problem of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the resulting modification has the property expressible by phi. We provide sufficient and necessary conditions on the structure of the prefix of phi specifying when the corresponding graph modification problem is fixed-parameter tractable (parameterized by k) and when it admits a polynomial kernel.

关键词： First-order logic Graph modification parameterized complexity Descriptive complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of vertex cover and edge cover with connectivity constraints

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期565卷 1-15页

作者： Fernau, Henning Fomin, Fedor V. Philip, Geevarghese Saurabh, Saket Univ Trier FB 4 Abt Informat D-54286 Trier Germany Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India Max Planck Inst Informat D-66123 Saarbrucken Germany

We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely VERTEX COVER and EDGE COVER. Specifically, we impose the additional requirement that each connected component of a solution have at least t vertices (resp. edges from the solution) for a fixed positive integer t, and call the problem t-TOTAL VERTEX COVER (resp. t-TOTAL EDGE COVER). In both cases the parameter k is the size of the solution. We show that both problems remain fixed-parameter tractable with these restrictions, with running times of the form O*(c(k)) for some constant c > 0 in each case, where the O* notation hides polynomial factors;for each fixed t >= 2, t-TOTAL VERTEX COVER has no polynomial kernel unless CoNP subset of NP/poly;for each fixed t >= 2, t-TOTAL EDGE COVER has a linear vertex kernel of size t + 1/t k. These results significantly improve earlier work on these problems. We illustrate the utility of the technique used to solve t-TOTAL VERTEX COVER, by applying it to derive an O*(c(k))-time FPT algorithm for the t-TOTAL EDGE DOMINATING SET problem. Our no-poly-kernel result for t-TOTAL VERTEX COVER, and the known NP-hardness result for t-TOTAL EDGE COVER, are in stark contrast to the fact that VERTEX COVER has a 2k vertex kernel, and that EDGE COVER is solvable in polynomial time. This illustrates how even the slightest connectivity requirement results in a drastic change in the tractability of problems-the curse of connectivity! (C) 2014 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Connectivity problems Kernel lower bounds Vertex cover Edge cover

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：