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

complexity results for rainbow matchings

THEORETICAL COMPUTER SCIENCE 2014年第0期524卷 27-33页

作者： Le, Van Bang Pfender, Florian Univ Rostock Inst Informat D-18055 Rostock Germany Univ Colorado Dept Math & Stat Denver CO 80202 USA

A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. We address the complexity issue of the following problem, MAX RAINBOW MATCHING: Given an edge-colored graph G, how large is the largest rainbow matching in G? We present several sharp contrasts in the complexity of this problem. We show, among others, that MAX RAINBOW MATCHING can be approximated by a polynomial algorithm with approximation ratio 2/3 - epsilon. MAX RAINBOW MATCHING is APX-complete, even when restricted to properly edge-colored linear forests without a 5-vertex path, and is solvable in polynomial time for edge-colored forests without a 4-vertex path. MAX RAINBOW MATCHING is APX-complete, even when restricted to properly edge-colored trees without an 8-vertex path, and is solvable in polynomial time for edge-colored trees without a 7-vertex path. MAX RAINBOW MATCHING is APX-complete, even when restricted to properly edge-colored paths. These results provide a dichotomy theorem for the complexity of the problem on forests and trees in terms of forbidding paths. The latter is somewhat surprising, since, to the best of our knowledge, no (unweighted) graph problem prior to our result is known to be NP-hard for simple paths. We also address the parameterized complexity of the problem. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Rainbow matching Computational complexity NP-completeness APX-completeness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for vertex partitioning problems parameterized by clique-width

引用

THEORETICAL COMPUTER SCIENCE 2014年 535卷 16-24页

作者： Oum, Sang-il Saether, Sigve Hortemo Vatshelle, Martin Korea Adv Inst Sci & Technol Dept Math Sci Taejon 305701 South Korea Univ Bergen Dept Informat N-5020 Bergen Norway

Many NP-hard problems, such as DOMINATING SET, are FPT parameterized by clique-width. For graphs of clique-width k given with a k-expression, DOMINATING SET can be solved in 4(k)n(O(1)) time. However, no FPT algorithm is known for computing an optimal k-expression. For a graph of clique-width k, if we rely on known algorithms to compute a (2(3k)-1)-expression via rank-width and then solving DOMINATING SET using the (2(3k)-1)-expression, the above algorithm will only give a runtime of 4(23k)n(O(1)). There have been results which overcome this exponential jump;the best known algorithm can solve DOMINATING SET in time 2(O(k2))n(O(1)) by avoiding constructing a k-expression Bui-Xuan et al. (2013) [7]. We improve this to 2O((k logk))n(O(1)). Indeed, we show that for a graph of clique-width k, a large class of domination and partitioning problems (LC-VSP), including DOMINATING SET, can be solved in 2(O(k log k))n(O(1)). Our main tool is a variant of rank-width using the rank of a 0-1 matrix over the rational field instead of the binary field. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Clique-width parameterized complexity Dynamic programming Generalized domination Rank-width

来源：评论

学校读者我要写书评

暂无评论

parameterized Domination in Circle Graphs

引用

THEORY OF COMPUTING SYSTEMS 2014年第1期54卷 45-72页

作者： Bousquet, Nicolas Goncalves, Daniel Mertzios, George B. Paul, Christophe Sau, Ignasi Thomasse, Stephan CNRS LIRMM AlGCo Project Team Montpellier France Univ Durham Sch Engn & Comp Sci Durham England UCBL CNRS ENS Lyon Lab LIPU LyonINRIA Lyon France

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely , where n=|V(G)|.

关键词： Circle graphs Domination problems parameterized complexity parameterized algorithms Dynamic programming Constrained domination

来源：评论

学校读者我要写书评

暂无评论

Local search for string problems: Brute-force is essentially optimal

引用

THEORETICAL COMPUTER SCIENCE 2014年 525卷 30-41页

作者： Guo, Jiong Hermelin, Danny Komusiewicz, Christian Univ Saarland D-66123 Saarbrucken Germany Ben Gurion Univ Negev Ind Management & Engn Dept IL-84105 Beer Sheva Israel Tech Univ Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

We address the problem of whether the brute-force procedure for the local improvement step in a local search algorithm can substantially be improved when applied to classical NP-hard string problems. We examine four of the more prominent problems in this domain: CLOSEST STRING, LONGEST COMMON SUBSEQUENCE, SHORTEST COMMON SUPERSEQUENCE, and SHORTEST COMMON SUPERSTRING. Herein, we consider arguably the most fundamental string distance measure, namely the Hamming distance, which has been applied in practical local search implementations for string problems. Our results indicate that for all four problems, the brute-force algorithm cannot be considerably improved. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Local search parameterized complexity parameterized intractability Closest String Longest Common Subsequence Shortest Common Supersequence Shortest Common Superstring

来源：评论

学校读者我要写书评

暂无评论

FO Model Checking on Posets of Bounded Width

FO Model Checking on Posets of Bounded Width

引用

IEEE Annual Symposium on Foundations of Computer Science

作者： Jakub Gajarsky Petr Hlineny Daniel Lokshtanov Jan Obdrzalek Sebastian Ordyniak M. S. Ramanujan Saket Saurabh Faculty of Informatics Masaryk University University of Bergen The Institute of Mathematical Sciences

ISBN: (纸本)9781467381925

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures - culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [CSL-LICS'14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset P of width w and an FO logic formula φ, and determines whether φ holds on P in time f(φ, w) · n~2.

关键词： First-order logic Partially ordered sets parameterized complexity Algorithmic meta-theorems

来源：评论

学校读者我要写书评

暂无评论

Searching for better fill-in

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2014年第7期80卷 1374-1383页

作者： Fomin, Fedor V. Villanger, Yngve Univ Bergen Dept Informat N-5008 Bergen Norway

MINIMUM FILL-IN is a fundamental and classical problem arising in sparse matrix computations. In terms of graphs it can be formulated as a problem of finding a triangulation of a given graph with the minimum number of edges. In this paper, we study the parameterized complexity of local search for the MINIMUM FILL-IN problem in the following form: Given a triangulation H of a graph G, is there a better triangulation, i.e. triangulation with less edges than H, within a given distance from H? We prove that this problem is fixed-parameter tractable (FPT) being parameterized by the distance from the initial triangulation, by providing an algorithm that in time f(k)vertical bar G vertical bar(O(1)) M decides if a better triangulation of G can be obtained by swapping at most k edges of H. Our result adds MINIMUM FILL-IN to the list of very few problems for which local search is known to be FPT. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Local search Minimum fill-in parameterized complexity Triangulation Chordal graph

来源：评论

学校读者我要写书评

暂无评论

KERNELIZATION LOWER BOUNDS BY CROSS-COMPOSITION

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2014年第1期28卷 277-305页

作者： Bodlaender, Hans L. Jansen, Bart M. P. Kratsch, Stefan Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway Tech Univ Berlin Dept Software Engn & Theoret Comp Sci D-10587 Berlin Germany

We introduce the framework of cross-composition for proving kernelization lower bounds. A classical problem L AND/OR-cross-composes into a parameterized problem Q if it is possible to efficiently construct an instance of Q with polynomially bounded parameter value that expresses the logical and or or of a sequence of instances of L. Building on work by Bodlaender et al. and using results of Fortnow and Santhanam, Dell and van Melkebeek, and Drucker, we show that if an NP-hard problem AND/OR-cross-composes into a parameterized problem Q, then Q does not admit a polynomial kernel unless NP subset of coNP/poly and the polynomial hierarchy collapses. Our technique generalizes and strengthens the techniques of using composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (nonstandard) parameterizations, e. g., Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. We have similar lower bounds for Feedback Vertex Set and Odd Cycle Transversal under structural parameterizations. After learning of our results, several teams of authors have successfully applied the cross-composition framework to different parameterized problems. For completeness, our presentation of the framework includes several extensions based on this follow-up work. For example, we show how a relaxed version of OR-cross-compositions may be used to give lower bounds on the degree of the polynomial in the kernel size.

关键词： kernelization kernel lower bounds parameterized complexity structural parameterization

来源：评论

学校读者我要写书评

暂无评论

Constant Thresholds Can Make Target Set Selection Tractable

引用

THEORY OF COMPUTING SYSTEMS 2014年第1期55卷 61-83页

作者： Chopin, Morgan Nichterlein, Andre Niedermeier, Rolf Weller, Mathias Univ Paris 09 LAMSADE Paris France TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

Target Set Selection, which is a prominent NP-hard problem occurring in social network analysis and distributed computing, is notoriously hard both in terms of achieving useful polynomial-time approximation as well as fixed-parameter algorithms. Given an undirected graph, the task is to select a minimum number of vertices into a "target set" such that all other vertices will become active in the course of a dynamic process (which may go through several activation rounds). A vertex, equipped with a threshold value t, becomes active once at least t of its neighbors are active;initially, only the target set vertices are active. We contribute further insights into the existence of islands of tractability for Target Set Selection by spotting new parameterizations characterizing some sparse graphs as well as some "cliquish" graphs and developing corresponding fixed-parameter tractability and (parameterized) hardness results. In particular, we demonstrate that upper-bounding the thresholds by a constant may significantly alleviate the search for efficiently solvable, but still meaningful special cases of Target Set Selection.

关键词： Spread of influence Dynamics in social networks parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

Consequence-based and fixed-parameter tractable reasoning in description logics

引用

ARTIFICIAL INTELLIGENCE 2014年第1期209卷 29-77页

作者： Simancik, Frantisek Motik, Boris Horrocks, Ian Univ Oxford Dept Comp Sci Oxford OX1 2JD England

In this paper we investigate the consequence-based algorithms that are nowadays commonly used for subsumption reasoning with description logic ontologies, presenting the following novel results. First, we present a very general consequence-based reasoning algorithm that can be instantiated so as to capture the essential features of the known algorithms. Second, we use this algorithm to develop a novel framework for a quantitative and parametric analysis of the complexity of subsumption reasoning in description logic ontologies. Our approach is based on the notion of a decomposition a graph-like structure that, roughly speaking, summarizes the models relevant during ontology reasoning. We identify width and length as decomposition parameters that determine the "level" of combinatorial reasoning. We prove that, when parameterized by a decomposition, our consequence-based algorithm runs in time that is fixed-parameter tractable in width and length. Third, we briefly discuss how length and width characterize the behavior of tableau algorithms. Fourth, we show that the width and length of existing ontologies are reasonably small, which, we believe, explains the good performance of consequence-based algorithms in practice. We thus obtain a sound foundation for a practical implementation of ontology reasoners, as well as a way to analyze the reasoners' performance. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Description logics parameterized complexity Treewidth

来源：评论

学校读者我要写书评

暂无评论

Digraph width measures in parameterized algorithmics

引用

DISCRETE APPLIED MATHEMATICS 2014年 168卷 88-107页

作者： Ganian, Robert Hlineny, Petr Kneis, Joachim Langer, Alexander Obdrzalek, Jan Rossmanith, Peter Masaryk Univ Fac Informat Brno 60200 Czech Republic Rhein Westfal TH Aachen D-52056 Aachen Germany

In contrast to undirected width measures such as tree-width, which have provided many important algorithmic applications, analogous measures for digraphs such as directed tree-width or DAG-width do not seem so successful. Several recent papers have given some evidence on the negative side. We confirm and consolidate this overall picture by thoroughly and exhaustively studying the complexity of a range of directed problems with respect to various parameters, and by showing that they often remain NP-hard even on graph classes that are restricted very beyond having small DAG-width. On the positive side, it turns out that clique-width (of digraphs) performs much better on virtually all considered problems, from the parameterized complexity point of view. (c) 2013 Elsevier B.V. All rights reserved.

关键词： Digraph parameterized complexity Tree-width DAG-width DAG-depth Clique-width

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：