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

Editing to a connected graph of given degrees

INFORMATION AND COMPUTATION 2017年 256卷 131-147页

作者： Golovach, Petr A. Univ Bergen Dept Informat N-5020 Bergen Norway

We consider the EDGE EDITING TO A CONNECTED GRAPH OF GIVEN DEGREES problem that asks, given a graph G, non-negative integers d,k and a function delta: V(G) ->{1,...,d}, whether it is possible to obtain a connected graph G' from G such that the degree of v is delta(v) for every vertex v by at most kedge editing operations. As the problem is NP-complete even if delta(v) = 2, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by d + k. For the special case delta(v) = d, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Graph editing Degree constraints Connectivity parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

SLIGHTLY SUPEREXPONENTIAL parameterized PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 2018年第3期47卷 675-702页

作者： Lokshtanov, Daniel Marx, Daniel Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control H-1518 Budapest Hungary Inst Math Sci Madras 600113 Tamil Nadu India

A central problem in parameterized algorithms is to obtain algorithms with running time f(k) center dot n(O(1)) such that f is as slow growing a function of the parameter k as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where f (k) is single-exponential, that is, c(k) for some constant c, which makes aiming for such a running time a natural goal for other problems as well. However, there are still plenty of problems where the f(k) appearing in the best-known running time is worse than single-exponential and it remained "slightly superexponential" even after serious attempts to bring it down. A natural question to ask is whether the f (k) appearing in the running time of the best-known algorithms is optimal for any of _ these problems. In this paper, we examine parameterized problems where f(k) is k(O(k)) = 2(O(k log k)) in the best-known running time, and for a number of such problems we show that the dependence on k in the running time cannot be improved to single-exponential. More precisely we prove the following tight lower bounds, for four natural problems, arising from three different domains: (1) In the CLOSEST STRING problem, given strings S-1,..., s(t) over an alphabet Sigma of length L each, and an integer d, the question is whether there exists a string s over E of length L, such that its hamming distance from each of the strings s,, 1 <= i <= t, is at most d. The pattern matching problem CLOSEST STRING is known to be solvable in times 2(O(d log d)) center dot n(O(1)) and 2(O(d log vertical bar Sigma vertical bar)) center dot n(O(1)). We show that there are no 2(O(d log d)) center dot n(O(1)) or 2(O(d log vertical bar Sigma vertical bar)) time algorithms, unless the Exponential Time Hypothesis (ETH) fails. (2) The graph embedding problem DISTORTION, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be solved in time 2(O(d log d)) center dot n

关键词： parameterized complexity exponential time hypothesis closest string distortion treewidth lower bound

来源：评论

学校读者我要写书评

暂无评论

Recognizing when a preference system is close to admitting a master list

引用

THEORETICAL COMPUTER SCIENCE 2024年 994卷

作者： Schlotter, Ildiko HUN REN Ctr Econ & Reg Stud Budapest Hungary Budapest Univ Technol & Econ Budapest Hungary

A preference system I is an undirected graph where vertices have preferences over their neighbors, and I admits a master list if all preferences can be derived from a single ordering over all vertices. We study the problem of deciding whether a given preference system I is close to admitting a master list based on three different distance measures. We determine the computational complexity of the following questions: can I be modified by (i) k swaps in the preferences, (ii) k edge deletions, or (iii) k vertex deletions so that the resulting instance admits a master list? We investigate these problems in detail from the viewpoint of parameterized complexity and of approximation. We also present two applications related to stable and popular matchings.

关键词： Preference system Master list parameterized complexity Approximation Preference swap Vertex/edge deletion

来源：评论

学校读者我要写书评

暂无评论

An O*(2.619^k) algorithm for 4-PATH VERTEX COVER

引用

DISCRETE APPLIED MATHEMATICS 2021年 291卷 1-14页

作者： Tsur, Dekel Ben Gurion Univ Negev Beer Sheva Israel

In the 4-PATH VERTEX COVER problem, the input is an undirected graph G and an integer k. The goal is to decide whether there is a set S of vertices of size at most k such that every path with 4 vertices in G contains at least one vertex of S. In this paper we give a parameterized algorithm for 4-PATH VERTEX COVER whose time complexity is 2.619(k). n(O)(1), where n denotes the number of vertices of the input graph. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized complexity Iterative compression Branching rules

来源：评论

学校读者我要写书评

暂无评论

Rank Reduction of Oriented Graphs by Vertex and Edge Deletions

引用

ALGORITHMICA 2018年第10期80卷 2757-2776页

作者： Meesum, Syed M. Saurabh, Saket HBNI Inst Math Sci Madras Tamil Nadu India Univ Bergen Bergen Norway

In this paper we continue our study of graph modification problems defined by reducing the rank of the adjacency matrix of the given graph, and extend our results from undirected graphs to modifying the rank of skew-adjacency matrix of oriented graphs. An instance of a graph modification problem takes as input a graph G and a positive integer k, and the objective is to either delete k vertices/edges or edit k edges so that the resulting graph belongs to a particular family of graphs. Given a fixed positive integer r, we define as the family of oriented graphs where for each , the rank of the skew-adjacency matrix of G is at most r. Using the family we do algorithmic study, both in classical and parameterized complexity, of the following graph modification problems: -Rank Vertex Deletion, -Rank Edge Deletion. We first show that both the problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time for -Rank Vertex Deletion, and an algorithm for -Rank Edge Deletion running in time . In addition to our FPT results we design polynomial kernels for these problems. Our main structural result, which is the fulcrum of all our algorithmic results, is that for a fixed integer r the size of any "reduced graph" in is upper bounded by . This result is of independent interest and generalizes a similar result of Kotlov and Lovasz regarding reduced oriented graphs of rank r.

关键词： Oriented graph Rank of skew-adjacency matrix Vertex deletion Edge deletion Fixed parameter tractable parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of solution extension of optimization problems

引用

THEORETICAL COMPUTER SCIENCE 2022年 904卷 48-65页

作者： Casel, Katrin Fernau, Henning Ghadikolaei, Mehdi Khosravian Monnot, Jerome Sikora, Florian Univ Potsdam Hasso Plattner Inst D-14482 Potsdam Germany Univ Trier Informat wissensch Theoret Informat Fachbereich 4 D-54286 Trier Germany Univ Paris 09 PSL Univ LAMSADE CNRS F-75016 Paris France

The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal vertex covers of a graph G = (V, E), one usually arrives at the problem to decide for a vertex set U subset of V (pre-solution), if there exists a minimal vertex cover S (i.e., a vertex cover S subset of V such that no proper subset of S is a vertex cover) with U subset of S (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework. In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP-complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP-completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Extension problems NP-hardness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

KERNELIZATION OF WHITNEY SWITCHES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第2期35卷 1298-1336页

作者： Fomin, Fedor, V Golovach, Petr A. Univ Bergen Dept Informat N-5020 Bergen Norway

A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic if and only if G can be transformed into H by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney's theorem: Given two 2-isomorphic graphs, can we transform one into another by applying at most k Whitney switches? This problem is already NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size O(k) and thus is fixed-parameter tractable when parameterized by k

关键词： Whitney switch 2-isomorphism parameterized complexity kernelization

来源：评论

学校读者我要写书评

暂无评论

Graph editing to a given degree sequence

引用

THEORETICAL COMPUTER SCIENCE 2017年 665卷 1-12页

作者： Golovach, Petr A. Mertzios, George B. Univ Bergen Dept Informat N-5020 Bergen Norway Univ Durham Sch Engn & Comp Sci Durham DH1 3HP England

We investigate the parameterized complexity of the graph editing problem called EDITING TO A GRAPH WITH A GIVEN DEGREE SEQUENCE Where the aim iS to obtain a graph With a given degree sequence sigma by at most k vertex deletions, edge deletions and edge additions. We show that the problem is W[1]-hard when parameterized by k for any combination of the allowed editing operations. From the positive side, we show that the problem can be solved in time 2 04 *+42)n2logn for n-vertex graphs, where Delta* = max sigma, i.e., the problem is FAT when parameterized by k + A*. We also show that EDITING TO A GRAPH. WITH A GIVEN DEGREE SEQUENCE has a polynomial kernel when parameterized by k + Delta* if only edge additions are allowed, and there is no polynomial kernel unless NP subset of co-NP/poly for all other combinations of the allowed editing operations. (C) 2016 Published by Elsevier B.V.

关键词： parameterized complexity Graph editing Degree sequence

来源：评论

学校读者我要写书评

暂无评论

Threshold dominating sets and an improved characterization of W

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期209卷 123-140页

作者： Downey, RG Fellows, MR Univ Victoria Dept Math Wellington New Zealand Univ Victoria Dept Comp Sci Victoria BC V8W 3P6 Canada

The THRESHOLD DOMINATING SET problem is that of determining for a graph G = (V,E) whether there is a subset V' subset of or equal to V of size k, such that for each vertex v is an element of V there are at least r elements of the closed neighborhood N[v] that belong to V'. We consider the complexity of the problem parameterized by the pair (k,r). It is trivial to observe that this is hard for W[2]. It can also be easily shown to belong to a natural extension W*[2] of W[2] defined in terms of circuit families of depth bounded by a function of the parameter. We prove membership in W[2] and thus W[2]-completeness. Using this as a starting point, we prove that W*[2] = W[2]. (C) 1998-Elsevier Science B.V. All rights reserved.

关键词： parameterized complexity dominating sets threshold computation satisfiability problems Boolean circuits

来源：评论

学校读者我要写书评

暂无评论

On Cutwidth parameterized by Vertex Cover

引用

ALGORITHMICA 2014年第4期68卷 940-953页

作者： Cygan, Marek Lokshtanov, Daniel Pilipczuk, Marcin Pilipczuk, Michal Saurabh, Saket Univ Warsaw Inst Informat PL-02097 Warsaw Poland Univ Calif San Diego La Jolla CA 92093 USA Univ Bergen Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 (k) n (O(1))). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 (n/2) n (O(1))) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NPaS dagger coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011;SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.

关键词： Cutwidth Vertex cover parameterization parameterized complexity Composition algorithms Polynomial kernel

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：