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

Beyond bidimensionality: parameterized subexponential algorithms on directed graphs

INFORMATION AND COMPUTATION 2013年 233卷 60-70页

作者： Dorn, Frederic Fomin, Fedor V. Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket SINTEF Energy Res Trondheim Norway Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, k-LEAF OUT-BRANCHING, which is to find an oriented spanning tree with at least k leaves, we obtain an algorithm solving the problem in time 2(O(root k log k))n + n(O(1)) on directed graphs whose underlying undirected graph excludes some fixed graph H as a minor. For the special case when the input directed graph is planar, the running time can be improved to 2(O(root k))n + n(O(1)). The second example is a generalization of the DIRECTED HAMILTONIAN PATH problem, namely k-INTERNAL OUT-BRANCHING, which is to find all oriented spanning tree with at least k internal vertices. We obtain an algorithm solving the problem in time 2(O(root k log k)) + n(O(1)) on directed graphs whose underlying undirected graph excludes some fixed apex graph H as a minor. Finally, we observe that on these classes of graphs, the k-DIRECTED PATH problem is solvable in time O((1 + epsilon)(k)n(f(epsilon))), for any epsilon > 0, where f is some function of epsilon. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem-specific combinatorial structures, and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs. (C) 2013 Elsevier Inc. All rights reserved.

关键词： parameterized algorithms Subexponential running time Directed graph Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Double-Exponential Lower Bound for the Distinct Vectors Problem

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2020年第4期22卷

作者： Pilipczuk, Marcin Sorge, Manuel Univ Warsaw Warsaw Poland

In the (binary) DISTINCT VECTORS problem we are given a binary matrix A with pairwise different rows and want to select at most k columns such that, restricting the matrix to these columns, all rows are still pairwise different. A result by Froese et al. [JCSS] implies a 2(2O(k)) center dot poly (vertical bar A vertical bar)-time brute-force algorithm for DISTINCT VECTORS. We show that this running time bound is essentially optimal by showing that there is a constant c such that the existence of an algorithm solving DISTINCT VECTORS with running time 2(O(2ck)) center dot poly (vertical bar A vertical bar) would contradict the Exponential Time Hypothesis.

关键词： feature selection data mining computational complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Symmetric assembly puzzles are hard, beyond a few pieces

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2020年 90卷

作者： Demaine, Erik D. Korman, Matias Ku, Jason S. Mitchell, Joseph S. B. Otachi, Yota van Renssen, Andre Roeloffzen, Marcel Uehara, Ryuhei Uno, Yushi MIT Cambridge MA 02139 USA Tufts Univ Medford MA 02155 USA SUNY Stony Brook Stony Brook NY 11794 USA Nagoya Univ Nagoya Aichi Japan Univ Sydney Sydney NSW Australia TU Eindhoven Eindhoven Netherlands JAIST Nomi Japan Osaka Prefecture Univ Osaka Japan

We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union is line symmetric? On the negative side, we show that the problem is strongly NP-complete even if the pieces are all polyominos. On the positive side, we show that the problem can be solved in polynomial time if the number of pieces is a fixed constant. (C) 2020 Published by Elsevier B.V.

关键词： Assembly puzzle NP-complete parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity of the Steiner Network Problem with Respect to the Number of Terminals 36

Complexity of the Steiner Network Problem with Respect to th...

引用

36th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Eiben, Eduard Knop, Dusan Panolan, Fahad Suchy, Ondrej Univ Bergen Dept Informat Bergen Norway TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic

ISBN: (纸本)9783959771009

In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subset of V (G) with vertical bar T vertical bar = q, and an (unweighted) directed request graph R with V (R) = T. Our task is to output a subgraph H subset of G of the minimum cost such that there is a directed path from s to t in H for all st is an element of A(R). It is known that the problem can be solved in time vertical bar V (G)vertical bar(O(vertical bar A(R)vertical bar)) [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time vertical bar V (G)vertical bar(o(vertical bar A(R)vertical bar)) even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time vertical bar V (G)vertical bar(o(q)), unless ETH fails. Therefore, there is a significant gap in the complexity with respect to q in the exponent. We show that Directed Steiner Network is solvable in time f(q) center dot vertical bar V (G)vertical bar(O(cg center dot q)), where cg is a constant depending solely on the genus of G and f is a computable function. We complement this result by showing that there is no f(q) center dot vertical bar V (G)vertical bar(o(q2 / log q)) algorithm for any function f for the problem on general graphs, unless ETH fails.

关键词： Directed Steiner Network Planar Graphs parameterized algorithms Bounded Genus Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

Tractable QBF by Knowledge Compilation 36

Tractable QBF by Knowledge Compilation

引用

36th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Capelli, Florent Mengel, Stefan Univ Lille INRIA UMR 9189 CRIStALCtr Rech Informat Signal & Automat Lille F-59000 Lille France CRIL CNRS UMR 8188 Lens France

ISBN: (纸本)9783959771009

We generalize several tractability results concerning the tractability of Quantified Boolean Formulas (QBF) with restricted underlying structure. To this end, we introduce a notion of width for structured DNNF which are a class of Boolean circuits heavily studied in knowledge compilation, a subarea of artificial intelligence. We then show that structured DNNF allow quantifier elimination with a size blow-up depending only on the width of the DNNF and not its size. Using known algorithms transforming restricted CNF-formulas into deterministic DNNF, we apply this result to generalize several results for counting and decision on QBF. We also complement these results with lower bounds that show that our definitions and results are essentially optimal in several senses.

关键词： QBF knowledge compilation parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized Complexity of Length-bounded Cuts and Multicuts

引用

ALGORITHMICA 2018年第12期80卷 3597-3617页

作者： Dvorak, Pavel Knop, Dusan Charles Univ Prague Fac Math & Phys Malostranske Namesti 25 Prague 11800 1 Czech Republic

We study the Minimum Length-Bounded Cut problem where the task is to find a set of edges of a graph such that after removal of this set, the shortest path between two prescribed vertices is at least L + 1 long. We show the problem can be computed in FPT time with respect to L and the tree-width of the input graph G as parameters and with linear dependence of vertical bar V(G)vertical bar (i.e., in time f (L, tw(G))vertical bar V(G)vertical bar for a computable function f). We derive an FPT algorithm for a more general multi-commodity length-bounded cut problem when additionally parameterized by the number of terminals. For the former problem we show a W[1]-hardness result when the parameterization is done by the path-width only (instead of the tree-width) and that this problem does not admit polynomial kernel when parameterized by path-width and L. We also derive an FPT algorithm for the Minimum LENGTH-BOUNDED Cut problem when parameterized by the tree-depth, thus showing an interesting behavior for this problem and parameters tree-depth and path-width.

关键词： Length-bounded cuts parameterized algorithms W[1]-hardness Polynomial kernel Tree-depth Tree-width

来源：评论

学校读者我要写书评

暂无评论

Lean Tree-Cut Decompositions: Obstructions and algorithms 36

Lean Tree-Cut Decompositions: Obstructions and Algorithms

引用

36th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Giannopoulou, Archontia C. Kwon, O-joung Raymond, Jean-Florent Thilikos, Dimitrios M. Tech Univ Berlin LaS Team Berlin Germany Incheon Natl Univ Dept Math Incheon South Korea Univ Montpellier CNRS LIRMM AlGCo Project Team Montpellier France

ISBN: (纸本)9783959771009

The notion of tree-cut width has been introduced by Wollan in [The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, 110: 47-66, 2015]. It is defined via tree-cut decompositions, which are tree-like decompositions that highlight small (edge) cuts in a graph. In that sense, tree-cut decompositions can be seen as an edge-version of tree-decompositions and have algorithmic applications on problems that remain intractable on graphs of bounded treewidth. In this paper, we prove that every graph admits an optimal tree-cut decomposition that satisfies a certain Menger-like condition similar to that of the lean tree decompositions of Thomas [A Menger-like property of tree-width: The finite case, Journal of Combinatorial Theory, Series B, 48(1): 67-76, 1990]. This allows us to give, for every k is an element of N, an upper-bound on the number immersion-minimal graphs of tree-cut width k. Our results imply the constructive existence of a linear FPT-algorithm for tree-cut width.

关键词： tree-cut width lean decompositions immersions obstructions parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

The Treewidth of Smart Contracts 19

The Treewidth of Smart Contracts

引用

34th ACM/SIGAPP Annual International Symposium on Applied Computing (SAC)

作者： Chatterjee, Krishnendu Goharshady, Amir Kafshdar Goharshady, Ehsan Kafshdar IST Austria Klosterneuburg Austria Ferdowsi Univ Mashhad Mashhad Razavi Khorasan Iran

ISBN: (纸本)9781450359337

Smart contracts are programs that are stored and executed on the Blockchain and can receive, manage and transfer money (cryptocurrency units). Two important problems regarding smart contracts are formal analysis and compiler optimization. Formal analysis is extremely important, because smart contracts hold funds worth billions of dollars and their code is immutable after deployment. Hence, an undetected bug can cause significant financial losses. Compiler optimization is also crucial, because every action of a smart contract has to be executed by every node in the Blockchain network. Therefore, optimizations in compiling smart contracts can lead to significant savings in computation, time and energy. Two classical approaches in program analysis and compiler optimization are intraprocedural and interprocedural analysis. In intraprocedural analysis, each function is analyzed separately, while interprocedural analysis considers the entire program. In both cases, the analyses are usually reduced to graph problems over the control flow graph (CFG) of the program. These graph problems are often computationally expensive. Hence, there has been ample research on exploiting structural properties of CFGs for efficient algorithms. One such well-studied property is the treewidth, which is a measure of tree-likeness of graphs. It is known that intraprocedural CFGs of structured programs have treewidth at most 6, whereas the interprocedural treewidth cannot be bounded. This result has been used as a basis for many efficient intraprocedural analyses. In this paper, we explore the idea of exploiting the treewidth of smart contracts for formal analysis and compiler optimization. First, similar to classical programs, we show that the intraprocedural treewidth of structured Solidity and Vyper smart contracts is at most 9. Second, for global analysis, we prove that the interprocedural treewidth of structured smart contracts is bounded by 10 and, in sharp contrast with classical program

关键词： Smart Contracts parameterized algorithms Treewidth Blockchain Compiler Optimization Program Analysis Control Flow Graphs

来源：评论

学校读者我要写书评

暂无评论

FPT algorithms to Enumerate and Count Acyclic and Totally Cyclic Orientations 10th

FPT Algorithms to Enumerate and Count Acyclic and Totally Cy...

引用

10th Latin and American algorithms, Graphs, and Optimization Symposium (LAGOS)

作者： Oliveira, Farley Soares Hiraishi, Hidefumi Imai, Hiroshi Univ Tokyo Dept Comp Sci Tokyo Japan

In this paper, we deal with counting and enumerating problems for two types of graph orientations: acyclic and totally cyclic orientations. Counting is known to be #P-hard for both of them. To circumvent this issue, we propose Fixed Parameter Tractable (FPT) algorithms. For the enumeration task, we construct a Binary Decision Diagram (BDD) to represent all orientations of the two kinds, instead of explicitly enumerating them. We prove that the running time of this construction is bounded by O*(2(pw2/4+o(PW2))) with respect to the pathwidth pw. We then develop faster FPT algorithms to count acyclic and totally acyclic orientations, running in O*(2(bw2/2+o(bw2))) time, where bw denotes the branch-width of the given graph. These counting algorithms are obtained by applying the observations in our enumerating algorithm to branch decomposition.

关键词： Acyclic Orientations Totally Cyclic Orientations parameterized algorithms FPT algorithms Path-width Branch-width Binary Decision Diagram

来源：评论

学校读者我要写书评

暂无评论

Mining Maximal Induced Bicliques using Odd Cycle Transversals 19

Mining Maximal Induced Bicliques using Odd Cycle Transversal...

引用

SIAM International Conference on Data Mining (SDM)

作者： Kloster, Kyle Sullivan, Blair D. Van der Poel, Andrew North Carolina State Univ Raleigh NC 27695 USA

ISBN: (纸本)9781611975673

Many common graph data mining tasks take the form of identifying dense subgraphs (e.g. clustering, clique-finding, etc). In biological applications, the natural model for these dense substructures is often a complete bipartite graph (biclique), and the problem requires enumerating all maximal bicliques (instead of identifying just the largest or densest). The best known algorithm in general graphs is due to Dias et al., and runs in time O(M vertical bar V vertical bar(4)), where M is the number of maximal induced bicliques (MIBs) in the graph. When the graph being searched is itself bipartite, Zhang et al. give a faster algorithm where the time per MIB depends on the number of edges in the graph. In this work, we present a new algorithm for enumerating MIBs in general graphs, whose run time depends on how "close to bipartite" the input is. Specifically, the runtime is parameterized by the size k of an odd cycle transversal (OCT), a vertex set whose deletion results in a bipartite graph. Our algorithm runs in time O(M vertical bar V parallel to E vertical bar k(2)3(k/3)), which is an improvement on Dias et al. whenever k <= 3 log(3) vertical bar V vertical bar. We implement our algorithm alongside a variant of Dias et al.'s in open-source C++ code, and experimentally verify that the OCT-based approach is faster in practice on graphs with a wide variety of sizes, densities, and OCT decompositions.

关键词： bicliques odd cycle transversal parameterized algorithms enumeration bipartite

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：