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

A subexponential PARAMETERIZED algorithm FOR PROPER INTERVAL COMPLETION

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第4期29卷 1961-1987页

作者： Bliznets, Ivan Fomin, Fedor V. Pilipczuk, Marcin Pilipczuk, Michal Russian Acad Sci Steklov Inst Math St Petersburg St Petersburg 196140 Russia Univ Bergen Dept Informat N-5008 Bergen Norway Univ Warsaw Inst Informat Warsaw Poland

In the Proper Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir, and Tarjan [SIAM J. Comput., 28 (1999), pp. 1906-1922], who showed an algorithm for the problem working in O(16(k).(n+m)) time. In this paper we present an algorithm with running time k(O(k2/3)) + O(nm(kn + m)), which is the first subexponential parameterized algorithm for Proper Interval Completion.

关键词： fixed-parameter tractability proper interval graphs proper interval completion subexponential algorithm

来源：评论

学校读者我要写书评

暂无评论

subexponential PARAMETERIZED algorithm FOR MINIMUM FILL-IN

引用

SIAM JOURNAL ON COMPUTING 2013年第6期42卷 2197-2216页

作者： Fomin, Fedor V. Villanger, Yngve Univ Bergen Bergen Norway

The MINIMUM FILL-IN problem is used to decide if a graph can be triangulated by adding at most k edges. In 1994, Kaplan, Shamir, and Tarjan showed that the problem is solvable in time O(2(O(k)) + k(2)nm) on graphs with n vertices and m edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving MINIMUM FILL-IN in time O(2(O(root k log k)) + k(2)nm). This substantially lowers the complexity of the problem. Techniques developed for MINIMUM FILL-IN can be used to obtain subexponential parameterized algorithms for several related problems, including MINIMUM CHAIN COMPLETION, CHORDAL GRAPH SANDWICH, and TRIANGULATING COLORED GRAPH.

关键词： chordal graph parameterized complexity subexponential algorithm

来源：评论

学校读者我要写书评

暂无评论

A subexponential PARAMETERIZED algorithm FOR DIRECTED SUBSET TRAVELING SALESMAN PROBLEM ON PLANAR GRAPHS

引用

SIAM JOURNAL ON COMPUTING 2022年第2期51卷 254-289页

作者： Marx, Daniel Pilipczuk, Marcin Pilipczuk, Michal Saarland Informat Campus CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany Univ Warsaw Inst Informat Warsaw Poland

There are numerous examples of the so-called "square root phenomenon" in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter k, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in O(root k) instead of O(k) (modulo standard complexity assumptions). We consider a classic optimization problem Subset Traveling Salesman, where we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of this problem in planar graphs, where the number k = |T| of terminals is regarded as the parameter. We show that Subset TSP can be solved in time 2(O(root k log k)) center dot n(O(1)) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014, SIAM, Philadelphia, 2014, pp. 1812-1830] with the same running time that worked only on undirected planar graphs with polynomially large integer weights.

关键词： planar graphs subexponential algorithm subset TSP

来源：评论

学校读者我要写书评

暂无评论

subexponential algorithms for Variants of Homomorphism Problem in String Graphs 1

引用

45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Okrasa, Karolina Rzazewski, Pawel Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland

ISBN: (数字)9783030307868

ISBN: (纸本)9783030307868;9783030307851

We consider the complexity of finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy for the problem: if H has no two vertices sharing two common neighbors, then the problem can be solved in time 2(O(n2/3 log n)), otherwise there is no algorithm working in time 2(o(n)), even in intersection graphs of segments, unless the ETH fails. This generalizes several known results concerning the complexity of computational problems in geometric intersection graphs. Then we consider two variants of graph homomorphism problem, called locally injective homomorphism and locally bijective homomorphism, where we require the homomorphism to be injective or bijective on the neighborhood of each vertex. We show that for each target graph H, both problems can always be solved in time 2(O(root n log n)) in string graphs. For the locally surjective homomorphism, defined analogously, the situation seems more complicated. We show the dichotomy theorem for simple connected graphs H with maximum degree 2. If H is isomorphic to P-3 or C-4, then the existence of a locally surjective homomorphism from a string graph with n vertices to H can be decided in time 2(O(n2/3 log3/2 n)), otherwise, assuming ETH, the problem cannot be solved in time 2(o(n)). As a byproduct, we obtain results concerning the complexity of variants of homomorphism problem in P-t-free graphs - in particular, the weighted homomorphism dichotomy, analogous to the one for string graphs.

关键词： Graph homomorphism subexponential algorithm String graphs Segment graphs

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for min-max 2-cluster editing

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第1期34卷 47-63页

作者： Chen, Li-Hsuan Wu, Bang Ye Natl Chung Cheng Univ Chiayi 621 Taiwan

For a given graph and an integer t, the Min-Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for , where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let . We show that the problem is polynomial-time solvable when roughly . When , we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in time for and in time for , where .

关键词： Parameterized algorithm Parameterized complexity Graph modification Clustering Randomized algorithm subexponential algorithm

来源：评论

学校读者我要写书评

暂无评论

Faster Parameterized algorithms for Deletion to Split Graphs

引用

algorithmICA 2015年第4期71卷 989-1006页

作者： Ghosh, Esha Kolay, Sudeshna Kumar, Mrinal Misra, Pranabendu Panolan, Fahad Rai, Ashutosh Ramanujan, M. S. Inst Math Sci Madras 600113 Tamil Nadu India Indian Inst Technol Madras 600036 Tamil Nadu India Chennai Math Inst Chennai Tamil Nadu India

An undirected graph is said to be split if its vertex set can be partitioned into two sets such that the subgraph induced on one of them is a complete graph and the subgraph induced on the other is an independent set. We initiate a systematic study of parameterized complexity of the problem of deleting the minimum number of vertices or edges from a given input graph so that the resulting graph is split. We give efficient fixed-parameter algorithms and polynomial sized kernels for the problem. More precisely, 1. for Split Vertex Deletion, the problem of determining whether there are k vertices whose deletion results in a split graph, we give an O* (2(k)) algorithm (O* () notation hides factors that are polynomial in the input size) improving on the previous best bound of . We also give an -sized kernel for the problem. 2. For Split Edge Deletion, the problem of determining whether there are k edges whose deletion results in a split graph, we give an algorithm. We also prove the existence of an kernel. In addition, we note that our algorithm for SPLIT EDGE DELETION adds to the small number of subexponential parameterized algorithms not obtained through bidimensionality (Demaine et al. in J. ACM 52(6): 866-893, 2005), and on general graphs.

关键词： Parameterized complexity Deletion problems Split graphs subexponential algorithm

来源：评论

学校读者我要写书评

暂无评论

Another Sub-exponential algorithm for the Simple Stochastic Game

引用

algorithmICA 2011年第4期61卷 1092-1104页

作者： Dai, Decheng Ge, Rong Tsinghua Univ Beijing 100084 Peoples R China Princeton Univ Princeton NJ 08544 USA

We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can be viewed as an evidence showing the hardness to approximate the value of simple stochastic games. We also present a randomized algorithm that runs in (O) over tilde(root|V(R)|!) time, where |V(R)| is the number of RANDOM vertices and (O) over tilde ignores polynomial terms. This algorithm is the fastest known algorithm when |V(R)| = omega(log n) and |V(R)| = o(root min|V(min)|, |V(max)|) and it works for general (non-stopping) simple stochastic games.

关键词： Simple stochastic game subexponential algorithm

来源：评论

学校读者我要写书评

暂无评论

subexponential-Time algorithms for Finding Large Induced Sparse Subgraphs

引用

algorithmICA 2021年第8期83卷 2634-2650页

作者： Novotna, Jana Okrasa, Karolina Pilipczuk, Michal Rzazewski, Pawel van Leeuwen, Erik Jan Walczak, Bartosz Charles Univ Prague Fac Math & Phys Prague Czech Republic Univ Warsaw Fac Math Informat & Mech Inst Informat Warsaw Poland Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands Jagiellonian Univ Fac Math & Comp Sci Dept Theoret Comp Sci Krakow Poland

Let C and D be hereditary graph classes. Consider the following problem: given a graph G is an element of D, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C. We prove that it can be solved in 2(o(n)) time, where n is the number of vertices of G, if the following conditions are satisfied: the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices;the graphs in D admit balanced separators of size governed by their density, e.g., O(Delta) or O(root m), where Delta and m denote the maximum degree and the number of edges, respectively;and the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D: a largest induced forest in a P-t-free graph can be found in 2 (O) over tilde (n(2/3)) time, for every fixed t;and a largest induced planar graph in a string graph can be found in 2 (O) over tilde (n(2/3)) time.

关键词： subexponential algorithm Feedback vertex set P-t-free graphs String graphs

来源：评论

学校读者我要写书评

暂无评论

Computing the tutte polynomial on graphs of bounded clique-width

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2006年第4期20卷 932-946页

作者： Gimenez, Omer Hlineny, Petr Noy, Marc Tech Univ Catalonia Dept Math Appl Barcelona 08034 Spain Masaryk Univ Fac Informat Brno 60200 Czech Republic

The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion of clique-width extends the definition of cographs ( graphs without induced P-4), and it is a more general notion than that of tree-width. We show a subexponential algorithm ( running in time expO(n(1-epsilon))) for computing the Tutte polynomial on graphs of bounded clique- width. In fact, our algorithm computes the more general U-polynomial.

关键词： Tutte polynomial cographs clique-width subexponential algorithm U polynomial

来源：评论

学校读者我要写书评

暂无评论

algorithms and Almost Tight Results for -Colorability of Small Diameter Graphs

引用

algorithmICA 2016年第1期74卷 385-414页

作者： Mertzios, George B. Spirakis, Paul G. Univ Durham Sch Engn & Comp Sci Durham England Univ Liverpool Dept Comp Sci Liverpool Merseyside England Comp Technol Inst GR-26110 Patras Greece Univ Patras Patras Greece

The -coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter . Moreover, assuming the Exponential Time Hypothesis (ETH), -coloring cannot be solved in time on graphs with vertices and diameter at most . In spite of extensive studies of the -coloring problem with respect to several basic parameters, the complexity status of this problem on graphs with small diameter, i.e. with diameter at most , or at most , has been an open problem. In this paper we investigate graphs with small diameter. For graphs with diameter at most , we provide the first subexponential algorithm for -coloring, with complexity . Furthermore we extend the notion of an articulation vertex to that of an articulation neighborhood, and we provide a polynomial algorithm for -coloring on graphs with diameter that have at least one articulation neighborhood. For graphs with diameter at most , we establish the complexity of -coloring by proving for every that -coloring is NP-complete on triangle-free graphs of diameter and radius with vertices and minimum degree . Moreover, assuming ETH, we use three different amplification techniques of our hardness results, in order to obtain for every subexponential asymptotic lower bounds for the complexity of -coloring on triangle-free graphs with diameter and minimum degree . Finally, we provide a -coloring algorithm with running time for arbitrary graphs with diameter , where is the number of vertices and (resp. ) is the minimum (resp. maximum) degree of the input graph. To the best of our knowledge, this is the first subexponential algorithm for graphs with and for graphs with and . Due to the above lower bounds of the complexity of -coloring, the running time of this algorithm is asymptotically almost tight when the minimum degree of the input graph is , where , as its time complexity is and the corresponding lower bound states that there is no -time algorithm.

关键词： 3-Coloring Graph diameter Graph radius subexponential algorithm NP-complete Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：