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

subexponential algorithms for variants of the homomorphism problem in string graphs

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年第0期109卷 126-144页

作者： Okrasa, Karolina Rzazewski, Pawel Warsaw Univ Technol Fac Math & Informat Sci Ul Koszykowa 75 PL-00662 Warsaw Poland

We consider subexponential algorithms finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy: if H has no two vertices sharing two common neighbors, then the problem can be solved in time 2(O)(n(2/3) log n). otherwise there is no subexponential algorithm, assuming the ETH. Then we consider locally constrained homomorphisms. We show that for each target graph H, the locally injective and locally bijective homomorphism problems can be solved in time 2(O)(root n log n) in string graphs. For locally surjective homomorphisms we show a dichotomy for H being a path or a cycle. If H is P-3 or C-4, then the problem can be solved in time 2(O)(n(2/3) log(3/2) n) in string graphs;otherwise, assuming the ETH, there is no subexponential algorithm. As corollaries, we obtain new results concerning the complexity of homomorphism problems in P-t-free graphs. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Graph homomorphism String graphs Segment graphs subexponential algorithms ETH

来源：评论

学校读者我要写书评

暂无评论

subexponential algorithms for partial cover problems

引用

INFORMATION PROCESSING LETTERS 2011年第16期111卷 814-818页

作者： Fomin, Fedor V. Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket Inst Math Sci Madras 600113 Tamil Nadu India Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif San Diego Dept CS & Engn San Diego CA 92103 USA

Partial Cover problems are optimization versions of fundamental and well-studied problems like VERTEX COVER and DOMINATING SET. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number k of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by k. It was recently shown by Amini et al. (2008) [1] that PARTIAL VERTEX COVER and PARTIAL DOMINATING SET are fixed parameter tractable on large classes of sparse graphs, namely H-minor-free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time 2(O(k))n(O(1)). During the last decade there has been an extensive study on parameterized subexponential algorithms. In particular, it was shown that the classical VERTEX COVER and DOMINATING SET problems can be solved in subexponential time on H-minor-free graphs. The techniques developed to obtain subexponential algorithms for classical problems do not apply to partial cover problems. It was left as an open problem by Amini et al. (2008) [1] whether there is a subexponential algorithm for PARTIAL VERTEX COVER and PARTIAL DOMINATING SET. In this paper, we answer the question affirmatively by solving both problems in time 2(O(root k))n(O(1)) not only on planar graphs but also on much larger classes of graphs, namely, apex-minor-free graphs. Compared to previously known algorithms for these problems our algorithms are significantly faster and simpler. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Parameterized algorithms subexponential algorithms Partial cover problems Partial Dominating Set

来源：评论

学校读者我要写书评

暂无评论

subexponential algorithms for Unique Games and Related Problems

Subexponential Algorithms for Unique Games and Related Probl...

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Arora, Sanjeev Barak, Boaz Steurer, David Princeton Univ Dept Comp Sci CCI Princeton NJ 08544 USA Microsoft Res & Princeton Univ Princeton NJ 08544 USA Microsoft Res Cambridge MA USA

ISBN: (纸本)9780769542447

We give a subexponential time approximation algorithm for the UNIQUE GAMES problem. The algorithms run in time that is exponential in an arbitrarily small polynomial of the input size, n(epsilon). The approximation guarantee depends on epsilon, but not on the alphabet size or the number of variables. We also obtain a subexponential algorithms with improved approximations for SMALL-SET EXPANSION and MULTICUT. For MAX CUT, SPARSEST CUT, and VERTEX COVER, we give subexponential algorithms with improved approximations on some interesting subclasses of instances. Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for the UNIQUE GAMES. While our results stop short of refuting the UGC, they do suggest that UNIQUE GAMES is significantly easier than NP-hard problems such as MAX 3SAT, MAX 3LIN, LABEL COVER and more, that are believed not to have a subexponential algorithm achieving a non-trivial approximation ratio. The main component in our algorithms is a new result on graph decomposition that may have other applications. Namely we show that for every epsilon > 0 and every regular n -vertex graph G, by changing at most epsilon fraction of G's edges, one can break G into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most n(epsilon) eigenvalues larger than 1 - eta, where eta depends polynomially on epsilon.

关键词： Approximation algorithms Unique Games subexponential algorithms Spectral Methods Eigenvalues Graph Decompositions Constraint Satisfaction Problems

来源：评论

学校读者我要写书评

暂无评论

subexponential Parameterized algorithms and Kernelization on Almost Chordal Graphs

引用

ALGORITHMICA 2021年第7期83卷 2170-2214页

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

We study algorithmic properties of the graph class CHORDAL-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from CHORDAL-ke. More precisely, we identify a large class of optimization problems on CHORDAL-ke solvable in time 2O((root k log k)) center dot n(O(1)). Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on CHORDAL-ke when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of CHORDAL-ke graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on CHORDAL-ke graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on CHORDAL-ke graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of CHORDAL-ke, namely, INTERVAL-ke and SPLIT-ke graphs.

关键词： Parameterized complexity Structural parameterization subexponential algorithms Kernelization Chordal graphs Fill-in Independent set Clique Coloring

来源：评论

学校读者我要写书评

暂无评论

subexponential PARAMETERIZED algorithms FOR PLANAR AND APEX-MINOR-FREE GRAPHS VIA LOW

引用

SIAM JOURNAL ON COMPUTING 2022年第6期51卷 1866-1930页

作者： Fomin, Fedor, V Lokshtanov, Daniel Marx, Daniel Pilipczuk, Marcin Pilipczuk, Michal Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA CISPA Helmholtz Ctr Informat Secur Saarland Informat Campus D-66123 Saarbrucken Germany Univ Warsaw Inst Informat PL-02097 Warsaw Poland Inst Math Sci Chennai 600113 India

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: A induces a subgraph of G of treewidth O( k log k), and for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2\scrO ( k log2 k) . n\scrO (1)) - 1, where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential-time parameterized algorithms for problems on planar graphs, usually with running time bound 2\scrO ( k log2 k)n\scrO (1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host LOCAL SEARCH, and SUBGRAPH ISOMORPHISM, among others. Up to this point, it was open whether these problems could be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

关键词： parameterized complexity subexponential algorithms treewidth planar graphs subgraph isomorphism

来源：评论

学校读者我要写书评

暂无评论

subexponential-Time algorithms for Maximum Independent Set in Pt-Free and Broom-Free Graphs

引用

ALGORITHMICA 2019年第2期81卷 421-438页

作者： Bacso, Gabor Lokshtanov, Daniel Marx, Daniel Pilipczuk, Marcin Tuza, Zsolt van Leeuwen, Erik Jan Hungarian Acad Sci Inst Comp Sci & Control Kende U 13-17 H-1111 Budapest Hungary Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Warsaw Inst Informat Banacha 2 PL-02097 Warsaw Poland Alfred Renyi Inst Math Realtanoda U 13-15 H-1053 Budapest Hungary Univ Pannonia Dept Comp Sci & Syst Technol Egyet U 10 H-8200 Veszprem Hungary Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3584 CC Utrecht Netherlands

In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on P-t-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t <= 5 (Lokshtanov et al., in: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5-7, 2014, pp 570-581, 2014), and an algorithm for t = 6 announced recently (Grzesik et al. in Polynomial-time algorithm for maximum weight independent set on P-6-free graphs. CoRR, arXiv:1707.05491, 2017). Here we study the existence of subexponential-time algorithms for the problem: we show that for any t >= 1, there is an algorithm for Maximum Independent Set on P-t-free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in 2(O(root tn log n)) time on P-t-free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. Scattered Set is the generalization of Maximum Independent Set where the vertices of the solution are required to be at distance at least d from each other. We give a complete characterization of those graphs H for which d-Scattered Set on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges): -If every component of H is a path, then d-Scattered Set on H-free graphs with n vertices and m edges can be solved in time 2(O(vertical bar V(H)vertical bar root n+m log(n+m))), even if d is part of the input. -Otherwise, assuming the Exponential-Time Hypothesis (ETH), there is no 2(o(n+m))-time algorithm for d-Scattered Set for any fixed d >= 3 on H-free graphs with n-vertices and m-edges.

关键词： Independent set subexponential algorithms Approximation Scattered set H-free graphs

来源：评论

学校读者我要写书评

暂无评论

On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs 59

On subexponential parameterized algorithms for Steiner Tree ...

引用

59th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Marx, Daniel Pilipczuk, Marcin Pilipczuk, Michal Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary Univ Warsaw Inst Informat Warsaw Poland

ISBN: (纸本)9781538642306

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 two classic optimization problems parameterized by the number of terminals. The STEINER TREE problem asks for a minimum-weight tree connecting a given set of terminals T in an edge-weighted graph. In the SUBSET TRAVELING SALESMAN problem we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of these problems in planar graphs, where the number k - vertical bar T vertical bar of terminals is regarded as the parameter. Our results are the following: SUBSET TSP can be solved in time 2(O(root k log k)).n(O(1)) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. Assuming the Exponential-Time Hypothesis, STEINER TREE on undirected planar graphs cannot be solved in time 2(o(k)).n(O(1)), even in the unit-weight setting. This lower bound makes STEINER TREE the first "genuinely planar" problem (i.e., where the input is only planar graph with a set of distinguished terminals) for which we can show that the square root phenomenon does not appear. STEINER TREE can be solved in time n(O(root k)).W on undirected planar graphs with maximum edge weight W. Note that this result is incomparable to the fact that the problem is known to be solvable in time 2(k).n(O(1)) even in general graphs. A direct corollary of the combination of our results for STEINER TREE is that this problem does not admit a parameter-preserving polynomial kernel on planar graphs un

关键词： Steiner tree subexponential algorithms parameterized algorithms planar graphs

来源：评论

学校读者我要写书评

暂无评论

subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering 57

Subexponential parameterized algorithms for planar and apex-...

引用

57th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Fomin, Fedor V. Lokshtanov, Daniel Marx, Daniel Pilipczuk, Marcin Pilipczuk, Michal Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary Univ Warsaw Inst Informat PL-00325 Warsaw Poland Inst Math Sci Bengaluru Karnataka India

ISBN: (纸本)9781509039333

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: A induces a subgraph of G of treewidth O(root k log k), and for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2(O(root k log2 k)) . n(O(1)))(-1), where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2(O(root k log2 k))n(O(1)). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph;examples of such problems include DIRECTED k-PATH, WEIGHTED k-PATH, VERTEX COVER LOCAL SEARCH, and SUBGRAPH ISOMORPHISM, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

关键词： subexponential algorithms planar graphs apex-minor-free graphs subgraph isomorphism

来源：评论

学校读者我要写书评

暂无评论

A subexponential algorithm for discrete logarithms over hyperelliptic curves of large genus over GF(q)

引用

THEORETICAL COMPUTER SCIENCE 1999年第1-2期226卷 7-18页

作者： Adleman, LM DeMarrais, J Huang, MD Univ So Calif Dept Comp Sci Los Angeles CA 90089 USA

There are well-known subexponential algorithms for finding discrete logarithms over finite fields. However, the methods which underlie these algorithms do not appear to be easily adapt able for finding discrete logarithms in the groups associated with elliptic curves and the Jacobians of hyperelliptic curves, except for very special cases (Menezes ct al., IEEE Trans. Inform. Theory 39 (1993) 1639-1646, Okamoto and Sakurai, Lecture Notes in Computer Science, vol. 576, Springer, Berlin, 1991). This has led to the development of cryptographic systems based on the discrete logarithm problem for such groups (Koblitz, Math. Comput. 48 (1987) 203-209, J. Cryptogr. 1 (1989) 139-150, Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer, Dordrecht, 1993, Miller, Lecture Notes in Computer Science, Springer, Berlin, 1986, pp. 417-426). In this paper a subexponential algorithm is presented for finding discrete logarithms in the group of rational points on the Jacobians of large genus hyperelliptic curves over prime fields. We give a heuristic argument that under certain assumptions, there exists a constant c less than or equal to 2.181 such that for g is an element of Z(>0) and odd prime powers q with log q less than or equal to (2g + 1)(1-epsilon) and 0 < epsilon = o(1), the algorithm computes discrete logarithms in the group of rational points on the Jacobian of a genus g hyperelliptic curve over GF(q) of the form y(2) = f(x) with deg(f) = 2g+1, within expected time Lq2g+1[1/2,c], or equivalently, L-qg[1/2,c'] with c' =root 2c. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： discrete logarithm elliptic and hyperelliptic curves subexponential algorithms

来源：评论

学校读者我要写书评

暂无评论

EPTAS and subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

引用

JOURNAL OF THE ACM 2021年第2期68卷 1–38页

作者： Bonamy, Marthe Bonnet, Edouard Bousquet, Nicolas Charbit, Pierre Giannopoulos, Panos Kim, Eun Jung Rzazewski, Pawel Sikora, Florian Thomasse, Stephan Univ Bordeaux LaBRI CNRS Bordeaux France Univ Lyon COMUE Univ Claude Bernard Lyon 1 LIP ENS LyonCNRS Lyon France Grenoble INP G SCOP Lab CNRS Grenoble France Univ Paris Diderot IRIF Paris France City Univ London GiCtr Dept Comp Sci London England Univ Paris 09 PSL Univ LAMSADE CNRS UMR F-75016 Paris France Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland Univ Warsaw Inst Informat Warsaw Poland Inst Univ France Lyon France

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for MAXIMUM CLIQE on unit disk graphs [Clark, Colbourn, Johnson;Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2((O) over tilde (n2/3)) for MAXIMUM CLIQE on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for MAX CLIQE on disk and unit ball graphs. MAX CLIQE on unit ball graphs is equivalent to finding, given a collection of points in R-3, a maximum subset of points with diameter at most some fixed value. In stark contrast, MAXIMUM CLIQE on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2(n1-epsilon), unless the Exponential Time Hypothesis fails.

关键词： Disk graph maximum clique computational complexity approximation algorithms subexponential algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：