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

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

来源：评论

学校读者我要写书评

暂无评论

Fixed-Parameter Tractability of Maximum Colored Path and Beyond

引用

ACM TRANSACTIONS ON algorithms 2024年第4期20卷 1-48页

作者： V. Fomin, Fedor Golovach, Petr a. Korhonen, Tuukka Simonov, Kirill Plattner, Hasso Stamoulis, Giannos Univ Bergen Dept Informat Bergen Norway Univ Potsdam Hasso Plattner Inst Potsdam Germany Univ Montpellier LIRMM CNRS Montpellier France

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored n-vertex undirected graph, vertices s and t , and an integer k , finds an ( s, t )-path containing at least k different colors in time 2 k n O (1). This is the first fpt algorithm for this problem, and it generalizes the algorithm of Bj & ouml;rklund, Husfeldt, and Taslaman on finding a path through k specified vertices. It also implies the first 2 k n O (1) time algorithm for finding an ( s, t )-path of length at least k . Our method yields fpt algorithms for even more general problems. For example, we consider the problem where the input consists of an n-vertex undirected graph G , a matroid M whose elements correspond to the vertices of G and which is represented over a finite field of order q , a positive integer weight function on the vertices of G , two sets of vertices S, T subset of V ( G ) , and integers p, k, w , and the task is to find p vertex-disjoint paths from S to T so that the union of the vertices of these paths contains an independent set of M of cardinality k and weight w , while minimizing the sum of the lengths of the paths. We give a 2 p+O(k 2 log (q+k)) n O( 1 ) w time randomized algorithm for this problem.

关键词： fpt algorithms finding long paths algebraic techniques in fpt

来源：评论

学校读者我要写书评

暂无评论

On the Parameterized Complexity of Bend-Minimum Orthogonal Planarity

引用

ALGORITHMICA 2024年第10期86卷 3231-3251页

作者： Di Giacomo, Emilio Didimo, Walter Liotta, Giuseppe Montecchiani, Fabrizio Ortali, Giacomo Univ Perugia Dept Engn Perugia Italy

Computing planar orthogonal drawings with the minimum number of bends is one of the most studied topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia in SIAM J Comput 31(2):601-625, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number b of bends, the number k of vertices of degree at most two, and the treewidth tw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{tw}$$\end{document} of the input graph (Di Giacomo et al. in J Comput Syst Sci 125:129-148, 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by b+k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b+k$$\end{document}. As a consequence, rectilinear planarity testing lies in fpt parameterized by the number of vertices of degree at most two. We also prove that our choice of parameters is minimal, as deciding if an orthogonal drawing with at most b bends exists is already NP-hard when k is zero (i.e., the problem is para-NP-hard parameterized in k);hence, there is neither an fpt nor an XP algorithm parameterized only by the parameter k (unless P = NP). In addition, we prove that the problem is W[1]-hard parameterized by k+tw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{

关键词： Orthogonal drawings Bend minimization Parameterized complexity fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity of Maximum Edge Colorable Subgraph

引用

ALGORITHMICA 2022年第10期84卷 3075-3100页

作者： Agrawal, Akanksha Kundu, Madhumita Sahu, Abhishek Saurabh, Saket Tale, Prafullkumar Indian Inst Technol Madras Chennai Tamil Nadu India Univ Bergen Bergen Norway HBNI Inst Math Sci Chennai Tamil Nadu India CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

A graph H is p-edge colorable if there is a coloring psi : E(H) -> {1, 2, ... , p}, such that for distinct uv, vw is an element of E(H), we have psi(uv) not equal psi(vw). The MAXIMUM EDGE-COLORABLE SUBGRAPH problem takes as input a graph G and integers 1 and p, and the objective is to find a subgraph H of G and a p-edge-coloring of H, such that vertical bar E(H)vertical bar >= l. We study the above problem from the viewpoint of Parameterized Complexity. We obtain fpt algorithms when parameterized by: (1) the vertex cover number of G, by using INTEGER LINEAR PROGRAMMING, and (2) 1, a randomized algorithm via a reduction to RAINBOW MATCHING, and a deterministic algorithm by using color coding, and divide and color. With respect to the parameters p + k, where k is one of the following: (1) the solution size,l, (2) the vertex cover number of G, and (3) 1-mm(G), where mm(G) is the size of a maximum matching in G;we show that the (decision version of the) problem admits a kernel with O(k . p) vertices. Furthermore, we show that there is no kernel of size O(k(1-epsilon) . f (p)), for any epsilon > 0 and computable function f, unless NP subset of coN P/poly.

关键词： Edge Coloring Kernelization fpt algorithms Kernel Lower Bound

来源：评论

学校读者我要写书评

暂无评论

A 2k-kernelization algorithm for vertex cover based on crown decomposition

引用

THEORETICAL COMPUTER SCIENCE 2018年 739卷 80-85页

作者： Li, Wenjun Zhu, Binhai Changsha Univ Sci & Technol Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Hunan Peoples R China Montana State Univ Gianforte Sch Comp Bozeman MT 59717 USA

We revisit crown decomposition for the Vertex Cover problem by giving a simple 2k-kernelization algorithm. Previously, a 2k kernel was known but it was computed using both crown decomposition and linear programming;moreover, with crown decomposition alone only a 3k kernel was known. Our refined crown decomposition carries some extra property and could be used for some other related problems. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Vertex cover Crown decomposition Kernelization fpt algorithms NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover

引用

DISCRETE APPLIED MATHEMATICS 2005年第1-3期152卷 229-245页

作者： Nishimura, N Ragde, P Thilikos, DM Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Politecn Cataluna Dept Llenguatges & Sistemas Informat E-08034 Barcelona Spain

Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. In particular, we consider the class W-k (G), where for each graph G in W-k(G), the removal of a set of at most k vertices from G results in a graph in the base graph class W. (If W is the class of edgeless graphs, W-k(G) is the class of graphs with bounded vertex cover.) When G, is a minor-closed class such that each graph in W has bounded maximum degree, and all obstructions of (minor-minimal graphs outside G) are connected, we obtain an O((g + k)vertical bar V(G)vertical bar + (fk)(k)) recognition algorithm for W-k(G), where g and f are constants (modest and quantified) depending on the class K If 9 is the class of graphs with maximum degree bounded by D (not closed under minors), we can still obtain a running time of O(vertical bar V(G)vertical bar(D+k) +k(D+k)(k+3)) for recognition of graphs in Wk(G). Our results are obtained by considering bounded-degree minor-closed classes for which all obstructions are connected graphs, and showing that the size of any obstruction for W-k (5) is O(tk(7) + t(7)k(2)), where t is a bound on the size of obstructions for W. A trivial corollary of this result is an upper bound of (k + 1) (k + 2) on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest. (c) 2005 Elsevier B.V. All rights reserved.

关键词： parameterized complexity graph minors fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Communication Complexity and Graph Families

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2019年第2期11卷 1–28页

作者： Kolay, Sudeshna Panolan, Fahad Saurabh, Saket Eindhoven Univ Technol NL-5612 AZ Eindhoven Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

Given a graph G and a pair (F-1, F-2) of graph families, the function GDISJ(G),(F1), (F2) takes as input, two induced subgraphs G(1) and G(2) Of G, such that G(1) is an element of F-1 and G2 is an element of F-2 and returns 1 if V(G(1)) boolean AND v (G(2)) = theta and 0 otherwise. We study the communication complexity of this problem in the two-party model. In particular, we look at pairs of hereditary graph families. We show that the communication complexity of this function, when the two graph families are hereditary, is sublinear if and only if there are finitely many graphs in the intersection of these two families. Then, using concepts from parameterized complexity, we obtain nuanced upper bounds on the communication complexity of GDISJ(G),(F1),(F2). A concept related to communication protocols is that of a (F-1, F-2)-separating family of a graph G. A collection F of subsets of V(G) is called a (F-1, F-2)-separating family for G, if for any two vertex disjoint induced subgraphs G(1) is an element of F-1 and G2 is an element of F-2, there is a set F is an element of F with V (G(1)) subset of F and V (G(2)) boolean AND F = theta. Given a graph G on n vertices, for any pair (F-1, F-2) of hereditary graph families with sublinear communication complexity for GDISJ(G),(F1),(F2), we, we give an enumeration algoritlun that finds a subexponential sized (F-1, F-2)-separating family. In fact, we give an enumeration algoritlun that finds a 2(o(k))n(O(1)) sized(F-1, F-2)-separating family, where k denotes the size of a minimtun sized set S of vertices such that V(G) \ S has a bipartition (V-1, V-2) with G[V-1] is an element of F-1 and G[V-2] is an element of F-2. We exhibit a wide range of applications for these separating families, to obtain combinatorial bounds, entuneration algorithms, as well as exact and FPI algorithms for several problems.

关键词： Communication complexity separating family fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2016年第1期8卷 1–28页

作者： Kratsch, Stefan Marx, Daniel Wahlstroem, Magnus Max Planck Inst Informat D-66123 Saarbrucken Germany Hungarian Acad Sci Inst Comp Sci & Control H-1051 Budapest Hungary

For a finite set Gamma of Boolean relations, MAX ONES SAT(Gamma) and EXACT ONES SAT(Gamma) are generalized satisfiability problems where every constraint relation is from Gamma, and the task is to find a satisfying assignment with at least/exactly k variables set to 1, respectively. We study the parameterized complexity of these problems, including the question whether they admit polynomial kernels. For MAX ONES SAT(Gamma), we give a classification into five different complexity levels: polynomial-time solvable, admits a polynomial kernel, fixed-parameter tractable, solvable in polynomial time for fixed k, and NP-hard already for k = 1. For EXACT ONES SAT(Gamma), we refine the classification obtained earlier by taking a closer look at the fixed-parameter tractable cases and classifying the sets Gamma for which EXACT ONES SAT(Gamma) admits a polynomial kernel.

关键词： CSP kernelization fpt algorithms complexity characterization

来源：评论

学校读者我要写书评

暂无评论

ON THE FINE-GRAINED COMPLEXITY OF RAINBOW COLORING

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第3期32卷 1672-1705页

作者： Kowalik, Lukasz Lauri, Juho Socala, Arkadiusz Univ Warsaw Inst Informat Fac Math Informat & Mech Warsaw Poland Tampere Univ Technol Tampere Finland Nokia Bell Labs Dublin Ireland

The RAINBOW k-COLORING problem asks whether the edges of a given graph can be colored in k colors so that every pair of vertices is connected by a rainbow path, i. e., a path with all edges of di ff erent colors. Our main result states that for any k >= 2, there is no algorithm for RAINBOW k-COLORING running in time 2(o)(n(3/2)), unless the exponential time hypothesis fails. Motivated by this negative result we consider two parameterized variants of the problem. In the Subset Rainbow k-COLORING problem, introduced by Chakraborty et al. [J. Comb. Optim., 21 (2009), pp. 330{347], we are additionally given a set S of pairs of vertices and we ask if there is a coloring in which all the pairs in S are connected by rainbow paths. We show that Subset RAINBOW k-COLORING is fixed parameter tractable (fpt) when parameterized by jSj. We also study the Maximum RAINBOW k-COLORING problem, where we are additionally given an integer q, and we ask if there is a coloring in which at least q anti-edges are connected by rainbow paths. We show that the problem is fpt when parameterized by q and has a kernel of size O (q) for every k >= 2, extending the result of Ananth, Nasre, and Sarpatwar, in FSTTCS, LIPIcs, Schloss Dagstuhl{Leibniz-Zentum fur Informatik, Dagstuhl, Germany, 2011, pp. 241{251. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical EDGE COLORING problem, where it is a major open question if a 2(O(n))-time algorithm exists.

关键词： graph coloring computational complexity lower bounds fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：