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

Saving colors and Max Coloring: Some fixed-parameter tractability results

THEORETICAL COMPUTER SCIENCE 2019年 758卷 30-41页

作者： Escoffier, Bruno Sorbonne Univ CNRS Lab Informat Paris 6 LIP6 UMR 7606 4 Pl Jussieu F-75005 Paris France

Max coloring is a well known generalization of the usual Min Coloring problem, widely studied from (standard) complexity and approximation viewpoints. Here, we tackle this problem under the framework of parameterized complexity. In particular, we first show to what extend the result of [3] - saving colors from the trivial bound of n on the chromatic number - extends to Max Coloring. Then we consider possible improvements of these results by considering the problem of saving colors/weight with respect to a better bound on the chromatic number. Finally, we consider the fixed parameterized tractability of Max Coloring in restricted graph classes under standard parameterization. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Graph coloring Parameterized complexity fpt algorithms Max coloring

来源：评论

学校读者我要写书评

暂无评论

COMPUTING THE TANDEM DUPLICATION DISTANCE IS NP-HARD

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第1期36卷 64-91页

作者： Lafond, Manuel Zhu, Binhai Zou, Peng Univ Sherbrooke Dept Comp Sci Sherbrooke PQ J1K 2R1 Canada Montana State Univ Gianforte Sch Comp Bozeman MT 59717 USA

In computational biology, tandem duplication is an important biological phenomenon which can occur either at the genome or at the DNA level. A tandem duplication takes a copy of a genome segment and inserts it right after the segment-this can be represented as the string operation AXB double right arrow AXXB. Tandem exon duplications have been found in many species such as human, fly, and worm and have been largely studied in computational biology. The tandem duplication (TD) distance problem we investigate in this paper is defined as follows: given two strings S and T over the same alphabet Sigma, compute the smallest sequence of TDs required to convert S to T. The natural question of whether the TD distance can be computed in polynomial time was posed in 2004 by Leupold et al. and had remained open, despite the fact that TDs have received much attention ever since. In this paper, we focus on the special case when all characters of S are distinct. This is known as the exemplar TD distance, which is of special relevance in bioinformatics. We first prove that this problem is NP-hard when the alphabet size is unbounded, settling the 16-year-old open problem. We then show how to adapt the proof to vertical bar Sigma vertical bar = 4, hence proving the NP-hardness of the TD problem for any vertical bar Sigma vertical bar >= 4. One of the tools we develop for the reduction is a new problem called Cost-Effective Subgraph, for which we obtain W[1]-hardness results that might be of independent interest. We finally show that computing the exemplar TD distance between S and T is fixed-parameter tractable. Our results open the door to many other questions, and we conclude with several open problems.

关键词： tandem duplication text processing formal languages computational genomics fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

EXACT AND FIXED PARAMETER TRACTABLE algorithms FOR MAX-CONFLICT-FREE COLORING IN HYPERGRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第2期32卷 1189-1208页

作者： Ashok, Pradeesha Dudeja, Aditi Kolay, Sudeshna Saurabh, Saket Int Inst Informat Technol Bangalore Karnataka India Rutgers State Univ New Brunswick NJ 08901 USA Eindhoven Univ Technol Eindhoven Netherlands Inst Math Sci Taramani India Univ Bergen Dept Informat Bergen Norway

Conflict-free coloring of hypergraphs is a very well studied question of theoretical and practical interest. For a hypergraph H = (U, F), a conflict-free coloring of H refers to a vertex coloring where every hyperedge has a vertex with a unique color, distinct from all other vertices in the hyperedge. In this paper, we initiate a study of a natural maximization version of this problem, namely, Max-CFC: For a given hypergraph H and a fixed r >= 2, color the vertices of U using r colors so that the number of hyperedges that are conflict-free colored is maximized. By previously known hardness results for conflict-free coloring, this maximization version is NP-hard. We study this problem in the context of both exact and parameterized algorithms. In the parameterized setting, we study this problem with respect to a natural parameter-the solution size. In particular, the question we study is the following: p-CFC: For a given hypergraph, can we conflict-free color at least k hyperedges with at most r colors, the parameter being the solution size k. We show that this problem is fixed parameter tractable by designing an algorithm with running time 2(O(k log log k+k log r))(n + m)(O(1)) using a novel connection to the Unique Coverage problem and applying the method of color coding in a nontrivial manner. For the special case for hypergraphs induced by graph neighborhoods we give a polynomial kernel. Finally, we give an exact algorithm for Max-CFC running in O(2(n+m)) time. All our algorithms, with minor modifications, work for a stronger version of conflict-free coloring, UNIQUE MAXIMUM COLORING.

关键词： conflict-free coloring unique-maximum coloring fpt algorithms maximization algorithms

来源：评论

学校读者我要写书评

暂无评论

On some matching problems under the color-spanning model

引用

THEORETICAL COMPUTER SCIENCE 2019年 786卷 26-31页

作者： Bereg, Sergey Ma, Feifei Wang, Wencheng Zhang, Jian Zhu, Binhai Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100080 Peoples R China Montana State Univ Gianforte Sch Comp Bozeman MT 59717 USA

Given a set of n points Q in the plane, each colored with one of the k given colors, a color-spanning set S subset of Q is a subset of k points with distinct colors. The minimum diameter color-spanning set (MDCS) is a color-spanning set whose diameter is minimum. Somehow symmetrically, the largest closest pair color-spanning set (LCPCS) is a color-spanning set whose closest pair is the largest. Both MDCS and LCPCS have been shown to be NP-complete, but whether they are fixed-parameter tractable (fpt) when k is a parameter is open. Motivated by this question, we consider the fpt tractability of some matching problems under this color-spanning model, where 2k is the parameter. We show that the following three problems are polynomially solvable (hence fpt): (1) MinSum Matching Color-Spanning Set, (2) MaxMin Matching Color-Spanning Set, and (3) MinMax Matching Color-Spanning Set. For the k-Multicolored Independent Matching problem, namely, computing a matching of 2k vertices in a graph such that the vertices of the edges in the matching do not share edges, we show that it is W[1]-hard. Finally, motivated by this problem, which is related to the parameterized independent set problem, we are able to prove that LCPCS is W[1]-hard. (C) 2018 Elsevier B.V. All rights reserved.

关键词： (Fixed-parameter) computational geometry Matching algorithms fpt algorithms Color-spanning model NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs

引用

NETWORKS 2024年第2期84卷 132-147页

作者： de Figueiredo, Celina M. H. Lopes, Raul de Melo, Alexsander A. Silva, Ana Univ Fed Rio Janeiro Rio De Janeiro Brazil PSL Univ Univ Paris Dauphine CNRS UMR7243 Paris France Univ Fed Ceara Fortaleza Brazil

Chordal graphs are the intersection graphs of subtrees of a tree, while interval graphs of subpaths of a path. Undirected path graphs, directed path graphs and rooted directed path graphs are intermediate graph classes, defined, respectively, as the intersection graphs of paths of a tree, of directed paths of an oriented tree, and of directed paths of an out branching. All of these path graphs have vertex leafage 2. Dominating Set, Connected Dominating Set, and Steiner tree problems are W[2]$$ \mathrm{W}\left[2\right] $$-hard parameterized by the size of the solution on chordal graphs, NP$$ \mathrm{NP} $$-complete on undirected path graphs, and polynomial-time solvable on rooted directed path graphs, and hence also on interval graphs. We further investigate the (parameterized) complexity of all these problems when constrained to chordal graphs, taking the vertex leafage and the aforementioned classes into consideration. We prove that Dominating Set, Connected Dominating Set, and Steiner tree are fpt$$ \mathrm{fpt} $$ on chordal graphs when parameterized by the size of the solution plus the vertex leafage, and that Weighted Connected Dominating Set is polynomial-time solvable on strongly chordal graphs. We also introduce a new subclass of undirected path graphs, which we call in-out rooted directed path graphs, as the intersection graphs of directed paths of an in-out branching. We prove that Dominating Set, Connected Dominating Set, and Steiner tree are solvable in polynomial time on this class, generalizing the polynomiality for rooted directed path graphs proved by Booth and Johnson (SIAM J. Comput. 11 (1982), 191-199.) and by White et al. (Networks 15 (1985), 109-124.).

关键词： chordal graphs dominating set fpt algorithms Steiner tree undirected path graphs

来源：评论

学校读者我要写书评

暂无评论

Obtaining planarity by contracting few edges

引用

THEORETICAL COMPUTER SCIENCE 2013年 476卷 38-46页

作者： Golovach, Petr A. van 't Hof, Pim Paulusma, Daniel Univ Bergen Dept Informat N-5020 Bergen Norway Univ Durham Sch Engn & Comp Sci Durham DH1 3HP England

The PLANAR CONTRACTION problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when param... 详细信息

关键词： Planar graphs Edge contractions fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

引用

ALGORITHMICA 2015年第1期71卷 120-138页

作者： Arvind, V. Das, Bireswar Koebler, Johannes Toda, Seinosuke Inst Math Sci Madras 600113 Tamil Nadu India Indian Inst Technol Gandhinagar Gandhi Sagar 382424 India Humboldt Univ Inst Informat D-10099 Berlin Germany Nihon Univ Tokyo Japan

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism, denoted CHI, which has running time (2 (b) N) (O(1)), where the parameter b is the maximum size of the color classes of the given hypergraphs and N is the input size. We also describe an fpt algorithm for a parameterized coset intersection problem that is used as a subroutine in our algorithm for CHI.

关键词： Fixed parameter tractability fpt algorithms Graph isomorphism Computational complexity

来源：评论

学校读者我要写书评

暂无评论

UPWARD SPIRALITY AND UPWARD PLANARITY TESTING

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2009年第4期23卷 1842-1899页

作者： Didimo, Walter Giordano, Francesco Liotta, Giuseppe Univ Perugia Dipartimento Ingn Elettron Informaz I-06125 Perugia Italy

A digraph is upward planar if it admits a planar drawing where all edges are monotone in the upward direction. It is known that the problem of testing a digraph for upward planarity is NP-complete in general. This paper describes an O(n(4))-time upward planarity testing algorithm for all digraphs that have a series-parallel structure, where n is the number of vertices of the input. This significantly enlarges the family of digraphs for which a polynomial-time testing algorithm is known. Furthermore, the study is extended to general digraphs, and a fixed parameter tractable algorithm for upward planarity testing is described, whose time complexity is O(d(t) . t . n(3) + d . t(2) . n + d(2) . n(2)) where t is the number of triconnected components of the digraph and d is an upper bound on the diameter of any split component of the digraph. Our results use the new notion of upward spirality that, informally speaking, is a measure of the "level of winding" that a triconnected component of a digraph G can have in an upward planar drawing of G.

关键词： graph drawing upward planarity fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimum common string partition revisited

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第4期23卷 519-527页

作者： Jiang, Haitao Zhu, Binhai Zhu, Daming Zhu, Hong Montana State Univ Dept Comp Sci Bozeman MT 59717 USA Shandong Univ Sch Comp Sci & Technol Jinan 250100 Peoples R China E China Normal Univ Coll Software Shanghai 200062 Peoples R China

Minimum Common String Partition (MCSP) has drawn much attention due to its application in genome rearrangement. In this paper, we investigate three variants of MCSP: MCSP (c) , which requires that there are at most c elements in the alphabet;d-MCSP, which requires the occurrence of each element to be bounded by d;and x-balanced MCSP, which requires the length of blocks being in range (n/k-x,n/k+x), where n is the length of the input strings, k is the number of blocks in the optimal common partition and x is a constant integer. We show that MCSP (c) is NP-hard when ca parts per thousand yen2. As for d-MCSP, we present an fpt algorithm which runs in O (au)((d!)(2k) ) time. As it is still unknown whether an fpt algorithm only parameterized on k exists for the general case of MCSP, we also devise an fpt algorithm for the special case x-balanced MCSP parameterized on both k and x.

关键词： Minimum common string partition Genomic distance Genome rearrangement NP-completeness fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Dual Parameterization of Weighted Coloring

引用

ALGORITHMICA 2020年第8期82卷 2316-2336页

作者： Araujo, Julio Campos, Victor A. Lima, Carlos Vinicius G. C. dos Santos, Vinicius Fernandes Sau, Ignasi Silva, Ana Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil Univ Montpellier LIRMM CNRS Montpellier France

Given a graph G, a properk-coloring of G is a partition c=(Si)i is an element of[1,k] of V(G) into k stable sets S1, horizontal ellipsis ,Sk. Given a weight function w:V(G)-> R+, the weight of a colorSi is defined as w(i)=maxv is an element of Siw(v) and the weight of a coloringc as w(c)= n-ary sumation i=1kw(i). Guan and Zhu (Inf Process Lett 61(2):77-81, 1997) defined the weighted chromatic number of a pair (G, w), denoted by sigma(G,w), as the minimum weight of a proper coloring of G. The problem of determining sigma(G,w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time no(logn) unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is sigma(G,w)<= n-ary sumation v is an element of V(G)w(v)-k? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50-61, 2016), who provided an fpt algorithm running in time 2O(klogk)center dot nO(1), and asked which kernel size can be achieved for the problem. We provide an fpt algorithm in time 9k center dot nO(1), and prove that no algorithm in time 2o(k)center dot nO(1) exists under the ETH. On the other hand, we present a kernel with at most (2k-1+1)(k-1) vertices, and rule out the existence of polynomial kernels unless NP subset of coNP/poly, even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

关键词： Weighted coloring Max coloring Parameterized complexity Dual parameterization fpt algorithms Polynomial kernels Split graphs Interval graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：