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

Symmetric assembly puzzles are hard, beyond a few pieces

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2020年 90卷 101648-101648页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

A note on algebraic techniques for subgraph detection

引用

INFORMATION PROCESSING LETTERS 2022年 176卷

作者： Brand, Cornelius Vienna Univ Technol Algorithms & Complex Grp Vienna Austria

The k-path problem asks whether a given graph contains a simple path of length k. Along with other prominent parameterized problems, it reduces to the problem of detecting multilinear terms of degree k (k-MLD), making the latter a fundamental problem in parameterized algorithms. This has generated significant efforts directed at devising fast deterministic algorithms for k-MLD, and there are now at least two independent approaches that yield the same record bound on the running time. Namely the combinatorial representative-set based approach of Fomin et al. (JACM'16), and the algebraic techniques of Pratt (FOCS'19) and Brand and Pratt (ICALP'21). In this note, we explore the relationship between the latter results, based on partial differentials, and a previous algebraic approach based on the exterior algebra (Brand, ESA'19;Brand, Dell and Husfeldt, STOC'18). We do so by studying the relevant algebraic objects. These are on the one hand (1) the subalgebras of the tensor square of the exterior algebra generated in degree one. On the other hand, we consider (2) the space of partial derivatives of generic determinants, and closely related, (3) the space of minors of generic matrices. We prove that (2) arises as a quotient of (1), and that there is an isomorphism between the objects (1) and (3). Hence, the techniques are essentially equivalent, and the quotient relation between (2) and both of (1) and (3) hints at a possible refinement of the techniques. (C) 2021 Published by Elsevier B.V.

关键词： parameterized algorithms Algebraic algorithms Exterior algebra Apolar algebra Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Local linear set on graphs with bounded twin cover number

引用

INFORMATION PROCESSING LETTERS 2021年 170卷 106118-106118页

作者： Knop, Dusan Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic

Inspired by recent results for the so-called fair and local linear problems, we define two problems, LOCAL LINEAR SET and LOCAL LINEAR VERTEX COVER. Here the task is to find a set of vertices X subset of V (which is a vertex cover) of the input graph (V, E) such that the local linear constraints l(v) <= vertical bar X boolean AND N(v)vertical bar <= u(v) hold for all v is an element of V;here, l(v) and u( v) are on the input. We prove that both problems are in FPT for the parameter twin cover number (using integer linear programming). (C) 2021 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Local linear constraints parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for restricted subset feedback vertex set in chordal and split graphs

引用

THEORETICAL COMPUTER SCIENCE 2024年 984卷

作者： Bai, Tian Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

The RESTRICTED SUBSET FEEDBACK VERTEX SET problem (R-SFVS) takes a graph G = (V, E), a terminal set T C V, an integer k as the input. The task is to determine whether there exists a subset S C V ⧵ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP-complete even when the input graph is restricted to split graphs. In this paper, we mainly show that R-SFVS in chordal , split graphs can be solved in 0(1.1550|V|) time and exponential space or in 0(1.1605|V|) time and polynomial space, significantly improving all previous results. As a by-product, we show that the MAXIMUM INDEPENDENT SET problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to VERTEX COVER, we obtain an 0*(1.2738k)-time parameterized algorithm and a tight 0(k2)-kernel for R-SFVS in chordal and split graphs.

关键词： Subset feedback vertex set Chordal graphs Split graphs Exact exponential algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals on Few Faces

引用

ACM TRANSACTIONS ON algorithms 2020年第3期16卷 28-28页

作者： Kisfaludi-Bak, Sandor Nederlof, Jesper van Leeuwen, Erik Jan Max Planck Inst Informat Saarland Informat CampusCampus E1 4 D-66123 Saarbrucken Germany Eindhoven Univ Technol Dept Math & Comp Sci Dolech 3 NL-5612 AZ Eindhoven Netherlands Univ Utrecht Dept Informat & Comp Sci Princetonpl 5 NL-3584 CC Utrecht Netherlands

The Steiner Tree problem is one of the most fundamental NP-complete problems, as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights and a subset of vertices (often called terminals);the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987] considers instances where the underlying graph is planar and all terminals can be covered by the boundary of k faces. Erickson et al. show that the problem can be solved by an algorithm using n(O(k)) time and n(O(k)) space, where n denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts. In this work, we give an algorithm for Planar Steiner Tree with running time 2(O(k)) n(O(root k)) with the above parameterization, using only polynomial space. Furthermore, we show that the running time of our algorithm is almost tight: We prove that there is no f(k)n(o(root k)) algorithm for Planar Steiner Tree for any computable function f, unless the Exponential Time Hypothesis fails.

关键词： Planar graphs Steiner tree exact algorithms parameterized algorithms exponential time hypothesis lower bound

来源：评论

学校读者我要写书评

暂无评论

FPT algorithms to Enumerate and Count Acyclic and Totally Cyclic Orientations

引用

Electronic Notes in Theoretical Computer Science 2019年 346卷 655-666页

作者： Farley Soares Oliveira Hidefumi Hiraishi Hiroshi Imai Department of Computer Science The University of Tokyo 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 pw 2 /4+ o (pw 2 ) ) with respect to the pathwidth pw. We then develop faster FPT algorithms to count acyclic and totally acyclic orientations, running in O* (2 bw 2 /2+o(bw 2 ) ) 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

来源：评论

学校读者我要写书评

暂无评论

Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable

引用

ACM TRANSACTIONS ON algorithms 2015年第4期11卷 28-28页

作者： Chitnis, Rajesh Cygan, Marek Hajiaghayi, Mohammataghi Marx, Daniel Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Warsaw Inst Informat PL-02097 Warsaw Poland Hungarian Acad Sci Inst Comp Sci & Control H-1111 Budapest Hungary

Given a graph G and an integer k, the FEEDBACK VERTEX SET (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of Mehlhorn in 1984. The fixed-parameter tractability (FPT) status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC '08, JACM '08) showed that it is fixed-parameter tractable by giving a 4(k)k! . n(O(1)) time algorithm. There are two subset versions of this problems: We are given an additional subset S of vertices (resp., edges), and we want to hit all cycles passing through a vertex of S (resp., an edge of S);the two variants are known to be equivalent in the parameterized sense. Recently, the SUBSET FVS problem in undirected graphs was shown to be FPT by Cygan et al. (ICALP'11, SIDMA'13) and independently by Kakimura et al. (SODA '12). We generalize the result of Chen et al. (STOC '08, JACM '08) by showing that a SUBSET FVS in directed graphs can be solved in time 2(O(k3)) . n(O(1)) (i.e., FPT parameterized by size k of the solution). By our result, we complete the picture for FVS problems and their subset versions in undirected and directed graphs. The technique of random sampling of important separators was used by Marx and Razgon (STOC '11, SICOMP '14) to show that UNDIRECTED MULTICUT is FPT, and it was generalized by Chitnis et al. (SODA '12, SICOMP '13) to directed graphs to show that DIRECTEDMULTIWAY CUT is FPT. In addition to proving the FPT of a DIRECTED SUBSET FVS, we reformulate the random sampling of important separators technique in an abstract way that can be used with a general family of transversal problems. We believe this general approach will be useful for showing the FPT of other problems in directed graphs. Moreover, we modify the probability distribution used in the technique to achieve better running time;in particular, this gives an improvement from 2(2O(k)) to 2(O(k

关键词： algorithms Theory parameterized algorithms important separators subset feedback vertex set directed graphs

来源：评论

学校读者我要写书评

暂无评论

Kernel(s) for Problems with no Kernel: On Out-Trees with Many Leaves

引用

ACM TRANSACTIONS ON algorithms 2012年第4期8卷 38-38页

作者： Binkele-Raible, Daniel Fernau, Henning Fomin, Fedor V. Lokshtanov, Daniel Saurabh, Saket Villanger, Yngve Univ Trier Fachbereich 4 Abt Informat D-54286 Trier Germany Univ Bergen Dept Informat N-5008 Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India

The k-LEAF OUT-BRANCHING problem is to find an out-branching, that is a rooted oriented spanning tree, with at least k leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the k-LEAF-OUT-BRANCHING problem. We give the first polynomial kernel for ROOTED k-LEAF-OUT-BRANCHING, a variant of k-LEAF-OUT-BRANCHING where the root of the tree searched for is also a part of the input. Our kernel with O(k(3)) vertices is obtained using extremal combinatorics. For the k-LEAF-OUT-BRANCHING problem, we show that no polynomial-sized kernel is possible unless coNP is in NP/poly. However, our positive results for ROOTED k-LEAF-OUT-BRANCHING immediately imply that the seemingly intractable k-LEAF-OUT-BRANCHING problem admits a data reduction to n independent polynomialsized kernels. These two results, tractability and intractability side by side, are the first ones separating Karp kernelization from Turing kernelization. This answers affirmatively an open problem regarding "cheat kernelization" raised by Mike Fellows and Jiong Guo independently.

关键词： Kernelization lower bounds max-leaf spanning tree out-branching parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic Programming for Graphs on Surfaces

引用

ACM TRANSACTIONS ON algorithms 2014年第2期10卷 8-8页

作者： Rue, Juanjo Sau, Ignasi Thilikos, Dimitrios M. CSIC UAM UC3M UCM Inst Ciencias Matemat Madrid 28049 Spain CNRS AlGCo Project Team Lab Informat Robot & Microelect Montpellier Montpellier France Univ Athens Dept Math Athens 15784 Greece

We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2(O(***) (k)) . n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called surface cut decomposition, generalizing sphere cut decompositions of planar graphs, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of noncrossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2(O(k)) . n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improvemost previous results in this direction.

关键词： Analysis of algorithms parameterized algorithms graphs on surfaces branchwidth dynamic programming polyhedral embeddings noncrossing partitions

来源：评论

学校读者我要写书评

暂无评论

Distortion is Fixed Parameter Tractable

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2013年第4期5卷 16-16页

作者： Fellows, Michael Fomin, Fedor V. Lokshtanov, Daniel Losievskaja, Elena Rosamond, Frances Saurabh, Saket Charles Darwin Univ Darwin NT Australia Univ Bergen Dept Informat Bergen Norway Univ Iceland Dept Comp Sci Reykjavik Iceland Inst Math Sci Madras Tamil Nadu India

We study low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let M = M(G) be the shortest path metric of an edge-weighted graph G, with the vertex set V(G) and the edge set E(G), on n vertices. We give the first fixed parameter tractable algorithm that for an unweighted graph metric M and integer d either constructs an embedding of M into the line with distortion at most d, or concludes that no such embedding exists. Our algorithm requires O(nd(4)(2d + 1)(2d)) time which is a significant improvement over the best previous algorithm that runs in time O(n(4d+2)d(O(1))). Because of its apparent similarity to the notoriously hard BANDWIDTH MINIMIZATION problem, we find it surprising that this problem turns out to be fixed parameter tractable. We extend our results on embedding unweighted graph metric into the line in two ways. First, we give an algorithm to construct small-distortion embeddings of weighted graph metrics. The running time of our algorithm is O(n(dW)(4)(2d + 1)(2dW)), where W is the largest edge weight of the input graph. To complement this result, we show that the exponential dependence on the maximum edge weight is unavoidable. In particular, we show that deciding whether a weighted graph metric M(G) with maximum weight W < vertical bar V(G)vertical bar can be embedded into the line with distortion at most d is NP-complete for every fixed rational d >= 2. This rules out any possibility of an algorithm with running time O((nW)(h(d))) where h is a function of d alone. Second, we consider more general host metrics for which analogous results hold. In particular, we prove that for any tree T with maximum degree Delta, embedding M into a shortest path metric of T is fixed parameter tractable, parameterized by (Delta, d).

关键词： algorithms Theory Embedding distortion tree parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：