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

20th International Conference on Computing and Combinatorics (COCOON)

作者： Jiang, Minghui Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 = 1. We also obtain some interesting results for the general problem SCSI-t. From the negati... 详细信息

ISBN: (纸本)9783319087825

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 <= i <= k, the problem SHORTEST COLOR-SPANNING t INTERVALS (SCSI-t) aims at finding t intervals to cover at least si points of each color i, such that the maximum length of the intervals is minimized. Chen and Misiolek introduced the problem SCSI-1, and presented an algorithm running in O(n) time if the input points are sorted. Khanteimouri et al. gave an O (n(2) logn) time algorithm for the special case of SCSI-2 with s(i) = 1 for all colors i. In this paper, we present an improved algorithm with running time of 0(n2) for SCSI-2 with arbitrary si >= 1. We also obtain some interesting results for the general problem SCSI-t. From the negative direction, we show that approximating SCSI-t within any ratio is NP-hard when t is part of the input, is W[2]-hard when t is the parameter, and is W[1]-hard with both t and k as parameters. Moreover, the NP-hardness and the W[2]-hardness with parameter t hold even if si = 1 for all i. From the positive direction, we show that SCSI-t with si = 1 for all i is fixed-parameter tractable with k as the parameter, and admits an exact algorithm running in 0 (2(k)n . max{k, logn}) time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Color-spanning objects Computational geometry Exact algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

A Randomized Polynomial Kernel for Subset Feedback Vertex Set 33

A Randomized Polynomial Kernel for Subset Feedback Vertex Se...

引用

33rd Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Hols, Eva-Maria C. Kratsch, Stefan Univ Bonn Inst Informat Bonn Germany

ISBN: (纸本)9783959770019

The SUBSET FEEDBACK VERTEX SET problem generalizes the classical FEEDBACK VERTEX SET problem and asks, for a given undirected graph G = (V, E), a set S subset of V, and an integer k, whether there exists a set X of at most k vertices such that no cycle in G - X contains a vertex of S. It was independently shown by Cygan et al. (ICALP '11, SIDMA '13) and Kawarabayashi and Kobayashi (JCTB '12) that SUBSET FEEDBACK VERTEX SET is fixed-parameter tractable for parameter k. Cygan et al. asked whether the problem also admits a polynomial kernelization. We answer the question of Cygan et al. positively by giving a randomized polynomial kernelization for the equivalent version where S is a set of edges. In a first step we show that EDGE SUBSET FEEDBACK VERTEX SET has a randomized polynomial kernel parameterized by vertical bar S vertical bar k with O(vertical bar S vertical bar(2)k) vertices. For this we use the matroid-based tools of Kratsch and Wahlstrom (FOCS '12). Next we present a preprocessing that reduces the given instance (G, S, k) to an equivalent instance (G', S', k') where the size of S' is bounded by O(k(4)). These two results lead to a polynomial kernel for SUBSET FEEDBACK VERTEX SET with O(k(9)) vertices.

关键词： parameterized complexity kernelization subset feedback vertex set

来源：评论

学校读者我要写书评

暂无评论

On the complexity of Computing the k-restricted Edge-connectivity of a Graph 41st

On the Complexity of Computing the <i>k</i>-restricted Edge-...

引用

41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Montejano, Luis Pedro Sau, Ignasi Univ Montpellier 2 Dept Math Montpellier France LIRMM CNRS AlGCo Project Team Montpellier France

ISBN: (纸本)9783662531747;9783662531730

The k-restricted edge-connectivity of a graph G, denoted by lambda(k)(G),is defined as the minimum size of an edge set whose removal leaves exactly two connected components each containing at least k vertices. This graph invariant, which can be seen as a generalization of a minimum edge-cut, has been extensively studied from a combinatorial point of view. However, very little is known about the complexity of computing lambda(k)(G). Very recently, in the parameterized complexity community the notion of good edge separation of a graph has been defined, which happens to be essentially the same as the k-restricted edge-connectivity. Motivated by the relevance of this invariant from both combinatorial and algorithmic points of view, in this article we initiate a systematic study of its computational complexity, with special emphasis on its parameterized complexity for several choices of the parameters. We provide a number of NP-hardness and W[1]-hardness results, as well as FPT-algorithms.

关键词： Graph cut k-restricted edge-connectivity Good edge separation parameterized complexity FPT-algorithm u polynomial kernel

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of editing graphs for bounded degeneracy

引用

THEORETICAL COMPUTER SCIENCE 2010年第34-36期411卷 3181-3187页

作者： Mathieson, Luke Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

We examine the parameterized complexity of the problem of editing a graph to obtain an r-degenerate graph. We show that for the editing operations vertex deletion and edge deletion, both separately and combined, the problem is W[P]-complete. and remains W[P]-complete even if the input graph is already (r + 1)-degenerate, or has maximum degree 2r + 1 for all r >= 2. We also demonstrate fixed-parameter tractability for several CLIQUE based problems when the input graph has bounded degeneracy. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems Computational complexity parameterized complexity Degenerate graphs Graph editing

来源：评论

学校读者我要写书评

暂无评论

(Meta) Kernelization

引用

JOURNAL OF THE ACM 2016年第5期63卷 44-44页

作者： Bodlaender, Hans L. Fomin, Fedor V. Lokshtanov, Daniel Penninkx, Eelko Saurabh, Saket Thilikos, Dimitrios M. Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TC Utrecht Netherlands Eindhoven Univ Technol NL-5600 MB Eindhoven Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India Univ Athens Dept Math GR-15784 Athens Greece CNRS LIRMM AlGCo Project Team F-75700 Paris France

In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k while preserving the answer. In this work, we give two meta-theorems on kernelization. The first theorem says that all problems expressible in counting monadic second-order logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.

关键词： Monadic second-order logic parameterized complexity embedded graphs preprocessing kernelization treewidth protrusions finite integer index Algorithms Design Theory

来源：评论

学校读者我要写书评

暂无评论

Model Checking Existential Logic on Partially Ordered Sets

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2016年第2期17卷 10-10页

作者： Bova, Simone Ganian, Robert Szeider, Stefan Vienna Univ Technol Algorithms & Complex Grp A-1060 Vienna Austria

We study the problem of checking whether an existential sentence (i.e., a first-order sentence in prefix form built using existential quantifiers and all Boolean connectives) is true in a finite partially ordered set (a poset). A poset is a reflexive, antisymmetric, and transitive digraph. The problem encompasses the fundamental embedding problem of finding an isomorphic copy of a poset as an induced substructure of another poset. Model checking existential logic is already NP-hard on a fixed poset;thus, we investigate structural properties of posets yielding conditions for fixed-parameter tractability when the problem is parameterized by the sentence. We identify width as a central structural property (the width of a poset is the maximum size of a subset of pairwise incomparable elements);our main algorithmic result is that model checking existential logic on classes of finite posets of bounded width is fixed-parameter tractable. We observe a similar phenomenon in classical complexity, in which we prove that the isomorphism problem is polynomial-time tractable on classes of posets of bounded width;this settles an open problem in order theory. We surround our main algorithmic result with complexity results on less restricted, natural neighboring classes of finite posets, establishing its tightness in this sense. We also relate our work with (and demonstrate its independence of) fundamental fixed-parameter tractability results for model checking on digraphs of bounded degree and bounded clique-width.

关键词： Partially ordered sets model checking width parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

引用

ACM TRANSACTIONS ON ALGORITHMS 2016年第2期12卷 21-21页

作者： Kim, Eun Jung Langer, Alexander Paul, Christophe Reidl, Felix Rossmanith, Peter Sau, Ignasi Sikdar, Somnath CNRS LAMSADE Paris Paris France Rhein Westfal TH Aachen LuF Theoret Informat D-52056 Aachen Germany CNRS LIRMM Montpellier Montpellier France LIRMM 161 Rue Ada F-34095 Montpellier 05 France

We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set X subset of V(G), called a treewidth-modulator, such that the treewidth of G-X is bounded by a constant. Our decomposition, called a protrusion decomposition, is the cornerstone in obtaining the following two main results. Our first result is that any parameterized graph problem (with parameter k) that has a finite integer index and such that YES-instances have a treewidth-modulator of size O(k) admits a linear kernel on the class of H-topological-minor-free graphs, for any fixed graph H. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus and H-minor-free graphs. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n-vertex graph G and a non-negative integer k, PLANAR-F-DELETION asks whether G has a set X subset of V(G) such that vertical bar X vertical bar <= k and G-X is H-minor-free for every H epsilon F. As our second application, we present the first single-exponential algorithm to solve PLANAR-F-DELETION. Namely, our algorithm runs in time 2())(O(k) . n(2), which is asymptotically optimal with respect to k. So far, single-exponential algorithms were only known for special cases of the family F.

关键词： parameterized complexity algorithmic meta-theorems sparse graphs graph minors hitting minors

来源：评论

学校读者我要写书评

暂无评论

A Completeness Theory for Polynomial (Turing) Kernelization

引用

ALGORITHMICA 2015年第3期71卷 702-730页

作者： Hermelin, Danny Kratsch, Stefan Soltys, Karolina Wahlstroem, Magnus Wu, Xi Ben Gurion Univ Negev Beer Sheva Israel Tech Univ Berlin Berlin Germany Max Planck Inst Informat D-66123 Saarbrucken Germany Univ London Egham Surrey England Univ Wisconsin Madison WI USA

The framework of Bodlaender et al. (J Comput Sys Sci 75(8):423-434, 2009) and Fortnow and Santhanam (J Comput Sys Sci 77(1):91-106, 2011) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, some issues are not addressed by this framework, including the existence of Turing kernels such as the "kernelization" of leaf out-branching that outputs instances each of size poly. Observing that Turing kernels are preserved by polynomial parametric transformations (PPTs), we define two kernelization hardness hierarchies by the PPT-closure of problems that seem fundamentally unlikely to admit efficient Turing kernelizations. This gives rise to the MK- and WK-hierarchies which are akin to the M- and W-hierarchies of parameterized complexity. We find that several previously considered problems are complete for the fundamental hardness class WK[1], including Min Ones -SAT , Binary NDTM Halting , Connected Vertex Cover , and Clique parameterized by . We conjecture that no WK[1]-hard problem admits a polynomial Turing kernel. Our hierarchy subsumes an earlier hierarchy of Harnik and Naor that, from a parameterized perspective, is restricted to classical problems parameterized by witness size. Our results provide the first natural complete problems for, e.g., their class;this had been left open.

关键词： parameterized complexity Kernelization Turing kernelization complexity hierarchies

来源：评论

学校读者我要写书评

暂无评论

Uniform vs. Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey

引用

ALGORITHMS 2016年第2期9卷 32-32页

作者： Bjorklund, Henrik Berglund, Martin Ericson, Petter Umea Univ Dept Comp Sci SE-90187 Umea Sweden

Parsing for mildly context-sensitive language formalisms is an important area within natural language processing. While the complexity of the parsing problem for some such formalisms is known to be polynomial, this is not the case for all of them. This article presents a series of results regarding the complexity of parsing for linear context-free rewriting systems and deterministic tree-walking transducers. We discuss the difference between uniform and nonuniform complexity measures and how parameterized complexity theory can be used to investigate how different aspects of the formalisms influence how hard the parsing problem is. The main results we survey are all hardness results and indicate that parsing is hard even for relatively small values of parameters such as rank and fan-out in a rewriting system.

关键词： mildly context-sensitive languages parsing formal languages parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Using Patterns to Form Homogeneous Teams

引用

ALGORITHMICA 2015年第2期71卷 517-538页

作者： Bredereck, Robert Koehler, Thomas Nichterlein, Andre Niedermeier, Rolf Philip, Geevarghese TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Univ Jena Jena Germany Max Planck Inst Informat D-66123 Saarbrucken Germany

Homogeneous team formation is the task of grouping individuals into teams, each of which consists of members who fulfill the same set of prespecified properties. In this theoretical work, we propose, motivate, and analyze a combinatorial model where, given a matrix over a finite alphabet whose rows correspond to individuals and columns correspond to attributes of individuals, the user specifies lower and upper bounds on team sizes as well as combinations of attributes that have to be homogeneous (that is, identical) for all members of the corresponding teams. Furthermore, the user can define a cost for assigning any individual to a certain team. We show that some special cases of our new model lead to NP-hard problems while others allow for (fixed-parameter) tractability results. For example, the problem is already NP-hard even if (i) there are no lower and upper bounds on the team sizes, (ii) all costs are zero, and (iii) the matrix has only two columns. In contrast, the problem becomes fixed-parameter tractable for the combined parameter "number of possible teams" and "number of different individuals", the latter being upper-bounded by the number of rows.

关键词： Team selection Team formation k-Anonymity Matrix modification problems NP-hardness parameterized complexity Fixed-parameter tractability Kernelization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：