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

Graph editing problems with extended regularity constraints

THEORETICAL COMPUTER SCIENCE 2017年 677卷 56-68页

作者： Mathieson, Luke Univ Newcastle Ctr Informat Based Med Bioinformat & Biomarker Di Callaghan NSW Australia

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. Crown Copyright (C) 2017 Published by Elsevier B.V. All rights reserved.

关键词： Graph algorithms Computational complexity Algorithms parameterized complexity Graph editing

来源：评论

学校读者我要写书评

暂无评论

On Kernelization and Approximation for the Vector Connectivity Problem

引用

ALGORITHMICA 2017年第1期79卷 96-138页

作者： Kratsch, Stefan Sorge, Manuel Univ Bonn Inst Informat Bonn Germany TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

In the Vector Connectivity problem we are given an undirected graph , a demand function , and an integer k. The question is whether there exists a set S of at most k vertices such that every vertex has at least vertex-disjoint paths to S;this abstractly captures questions about placing servers or warehouses relative to demands. The problem is -hard already for instances with (Cicalese et al., Theoretical Computer Science '15), admits a log-factor approximation (Boros et al., Networks '14), and is fixed-parameter tractable in terms of k (Lokshtanov, unpublished '14). We prove several results regarding kernelization and approximation for Vector Connectivity and the variant Vector d-Connectivity where the upper bound d on demands is a fixed constant. For Vector d-Connectivity we give a factor d-approximation algorithm and construct a vertex-linear kernelization, that is, an efficient reduction to an equivalent instance with vertices. For Vector Connectivity we have a factor -approximation and we can show that it has no kernelization to size polynomial in k or even unless , which shows that is optimal for Vector d-Connectivity. Finally, we give a simple randomized fixed-parameter algorithm for Vector Connectivity with respect to k based on matroid intersection.

关键词： parameterized complexity Approximation Graph algorithms Kernelization NP-hard problem Separators

来源：评论

学校读者我要写书评

暂无评论

1.5D terrain guarding problem parameterized by guard range

引用

THEORETICAL COMPUTER SCIENCE 2017年 661卷 65-69页

作者： Khodakarami, Farnoosh Didehvar, Farzad Mohades, Ali Amirkabir Univ Technol Dept Math & Comp Sci Lab Algorithms & Computat Geometry Tehran Iran

The 1.5D terrain guarding problem examines a 1.5D terrain as an x-monotone polygonal chain in a plane to find the minimum guarding set for a given input terrain. This problem is NP-complete. In real world applications, guard power is limited and can only cover things within a range. Considering this limitation, the present study introduces the "terrain guard range" as a new geometric parameter by discretizing the definition of range, then presents a fixed-parameter algorithm to demonstrate that the 1.5D terrain guarding problem is fixed-parameter tractable with respect to the introduced parameter. (C) 2016 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Dynamic programming Guarding 1.5D terrain

来源：评论

学校读者我要写书评

暂无评论

On two extensions of equimatchable graphs

引用

DISCRETE OPTIMIZATION 2017年 26卷 112-130页

作者： Deniz, Zakir Ekim, Tinaz Hartinger, Tatiana Romina Milanic, Martin Shalom, Mordechai Suleyman Demirel Univ Dept Math Isparta Turkey Bogazici Univ Dept Ind Engn Istanbul Turkey Univ Primorska UP IAM Muzejski Trg 2 SI-6000 Koper Slovenia Univ Primorska UP FAMNIT Glagoljaska 8 SI-6000 Koper Slovenia TelHai Coll IL-12210 Upper Galilee Israel

A graph is said to be equimatchable if all its maximal matchings are of the same size. In this work we introduce two extensions of the property of equimatchability by defining two new graph parameters that measure how far a graph is from being equimatchable. The first one, called the matching gap, measures the difference between the sizes of a maximum matching and a minimum maximal matching. The second extension is obtained by introducing the concept of equimatchable sets;a set of vertices in a graph G is said to be equimatchable if all maximal matchings of G saturating the set are of the same size. Noting that G is equimatchable if and only if the empty set is equimatchable, we study the equimatchability defect of the graph, defined as the minimum size of an equimatchable set in it. We develop several inapproximability and parameterized complexity results and algorithms regarding the computation of these two parameters, a characterization of graphs of unit matching gap, exact values of the equimatchability defect of cycles, and sharp bounds for both parameters. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Minimum maximal matching Equimatchable graph Edge dominating set Gallai-Edmonds decomposition parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of computing the k-restricted edge-connectivity of a graph

引用

THEORETICAL COMPUTER SCIENCE 2017年 662卷 31-39页

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

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. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Graph cut k-Restricted edge-connectivity Good edge separation parameterized complexity FPT-algorithm Polynomial kernel

来源：评论

学校读者我要写书评

暂无评论

Fixed-Parameter Tractable Distances to Sparse Graph Classes

引用

ALGORITHMICA 2017年第1期79卷 139-158页

作者： Bulian, Jannis Dawar, Anuj Univ Cambridge Comp Lab Cambridge England

We show that for various classes of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph G to is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is . The second shows that determining the elimination distance of a graph G to a minor-closed class is . We demonstrate that several prior results (of Golovach, Moser and Thilikos and Mathieson) on the fixed-parameter tractability of distance measures are special cases of our first method.

关键词： Fixed-parameter tractable parameterized complexity Graph theory Sparse graphs Nowhere dense Excluded minor Minor-closed Deletion distance Elimination distance Distance

来源：评论

学校读者我要写书评

暂无评论

Finding Points in General Position

引用

International Journal of Computational Geometry & Applications 2018年第4期27卷 277-296页

作者： Vincent Froese Iyad Kanj André Nichterlein Rolf Niedermeier Institut für Softwaretechnik und Theoretische Informatik TU Berlin Germany School of Computing DePaul University Chicago USA

We study the General Position Subset Selection problem: Given a set of points in the plane, find a maximum-cardinality subset of points in general position. We prove that General Position Subset Selection is NP-hard, APX-hard, and present several fixed-parameter tractability results for the problem as well as a subexponential running time lower bound based on the Exponential Time Hypothesis.

关键词： Computational complexity parameterized complexity kernelization hardness of approximation point line cover

来源：评论

学校读者我要写书评

暂无评论

Separating sets of strings by finding matching patterns is almost always hard

引用

THEORETICAL COMPUTER SCIENCE 2017年 665卷 73-86页

作者： Lancia, Giuseppe Mathieson, Luke Moscato, Pablo Univ Udine Dipartimento Matemat & Informat Via Sci 206 I-33100 Udine Italy Univ Newcastle Sch Elect Engn & Comp Sci Callaghan NSW 2308 Australia

We study the complexity of the problem of searching for a set of patterns that separate two given sets of strings. This problem has applications in a wide variety of areas, most notably in data mining, computational biology, and in understanding the complexity of genetic algorithms. We show that the basic problem of finding a small set of patterns that match one set of strings but do not match any string in a second set is difficult (NP-complete, W[2]-hard when parameterized by the size of the pattern set, and APX-hard). We then perform a detailed parameterized analysis of the problem, separating tractable and intractable variants. In particular we show that parameterizing by the size of pattern set and the number of strings, and the size of the alphabet and the number of strings give FPT results, amongst others. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Pattern identification parameterized complexity Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Solving Hamiltonian Cycle by an EPT algorithm for a non-sparse parameter

引用

DISCRETE APPLIED MATHEMATICS 2017年 228卷 88-97页

作者： Saether, Sigve Hortemo Univ Bergen Dept Informat Bergen Norway

Many hard graph problems, such as Hamiltonian Cycle, become FPT when parameterized by treewidth, a parameter that is bounded only on sparse graphs. When parameterized by the more general parameter clique-width, Hamiltonian Cycle becomes Will-hard, as shown by Fomin et al. (2010). S ae ther and Telle address this problem in their paper (S ae ther and Telle, 2016). by introducing a new parameter, split-matching-width, which lies between treewidth and clique-width in terms of generality. They show that even though graphs of restricted split-matching-width might be dense, solving problems such as Hamiltonian Cycle can be done in FPT time. Recently, it was shown that Hamiltonian Cycle parameterized by treewidth is in EPT (Bodlaender et al., 2013;Fomin et al., 2014), meaning it can be solved in n(circle dot(1))2(circle dot(k))-time. In this paper, using tools from Fomin et al. (2014), we show that also parameterized by split-matching-width Hamiltonian Cycle is EPT. To the best of our knowledge, this is the first EPT algorithm for any "globally constrained" graph problem parameterized by a non-trivial and non-sparse structural parameter. To accomplish this, we also give an algorithm constructing a branch decomposition approximating the minimum split-matching-width to within a constant factor. Combined, these results show that the algorithms in S ae ther and Telle (2016) for Edge Dominating Set, Chromatic Number and Max Cut all can be improved. In fact, using our new approximation algorithm, under the Exponential Time Hypothesis, the Hamiltonian Cycle algorithm of this paper, and the three algorithms for MaxCut, Edge Dominating Set, and Chromatic Number, are asymptotically optimal. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Hamiltonian Cycle parameterized complexity Split-matching-width EPT

来源：评论

学校读者我要写书评

暂无评论

The complexity of degree anonymization by graph contractions

引用

INFORMATION AND COMPUTATION 2017年 256卷 212-225页

作者： Talmon, Nimrod Hartung, Sepp Tech Univ Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

We study the computational complexity of k-anonymizing a given graph by as few graph contractions as possible. A graph is said to be k-anonymous if for every vertex in it, there are at least k - 1 other vertices with exactly the same degree. The general degree anonymization problem is motivated by applications in privacy-preserving data publishing, and was studied to some extent for various graph operations (most notable operations being edge addition, edge deletion, vertex addition, and vertex deletion). We complement this line of research by studying the computational complexity of degree anonymization by graph contractions. We consider several variants of graph contractions, which are operations of interest, for example, in the contexts of social networks and clustering algorithms. We show that the problem of degree anonymization by graph contractions is NP-hard even for some very restricted inputs, and identify some fixed-parameter tractable cases. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Computational complexity parameterized complexity Fixed-parameter tractability Privacy Data publishing Graph modifications Degree-constrained editing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：