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

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

来源：评论

学校读者我要写书评

暂无评论

Min-max coverage problems on tree-like metrics 12

Min-max coverage problems on tree-like metrics

引用

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

作者： Aaron, Eric Hebert-Johnson, Ursula Krizanc, Danny Lokshtanov, Daniel Colby Coll Waterville ME 04901 USA Univ Calif Santa Barbara Santa Barbara CA 93106 USA Wesleyan Univ Middletown CT 06457 USA

We consider a number of min-max coverage problems. In each problem, the input is an unweighted graph G and an integer k, and possibly some additional information, such as a root vertex r. In the MIN-MAX Path Cover problem, the task is to cover all vertices of the graph by k walks, minimizing the length of the longest walk. The variant of MIN-MAX Path Cover in which all walks start and end at the same prescribed root vertex r is called the k-TRAVELING SALESMEN PROBLEM. In the MIN-MAX TREE COVER problem, the task is to cover all vertices of the graph by k trees, minimizing the size (number of edges) of the largest tree. In the rooted version, MIN-MAX k-ROOTED TREE COVER, the input also contains k roots r(1), . . . , r(k), and the ith tree must contain the root r(i). These four problems are all known to be APX-hard and to admit a constant-factor approximation. In this paper, we initiate the systematic study of these problems on trees and, more generally, on graphs of constant treewidth. As opposed to most graph problems, all four of the above coverage problems remain NP-hard even when G is a tree. We obtain an n(O(k))-time exact algorithm for all four problems on graphs of bounded treewidth. Our main contribution is a quasi-polynomial-time approximation scheme (QPTAS) for the k-TRAVELING SALESMEN PROBLEM, MIN-MAX PATH COVER, and MIN-MAX TREE COVER on graphs of bounded treewidth.(C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://***/licenses/by-nc-nd/4.0)

关键词： Approximation algorithms parameterized algorithms Min-max coverage Treewidth Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Kernelization for Graph Packing Problems via Rainbow Matching 34

Kernelization for Graph Packing Problems via Rainbow Matchin...

引用

34th ACM-SIAM Annual Symposium on Discrete algorithms (SODA)

作者： Bessy, Stephane Bougeret, Marin Thilikos, Dimitrios M. Wiederrecht, Sebastian Univ Montpellier CNRS LIRMM Montpellier France Inst for Basic Sci Korea Discrete Math Grp Daejeon South Korea

ISBN: (纸本)9781611977554

We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021]. We apply the rainbow matching technique on two (di)graph packing problems, namely the Triangle-Packing in Tournament problem (TPT), where we ask for a packing of k directed triangles in a tournament, and the Induced 2-Path-Packing (I2PP) where we ask for a packing of k induced paths of length two in a graph. The existence of a sub-quadratic kernels for these problems was proven for the first time in [Fomin, Le, Lokshtanov, Saurabh, Thomasse, Zehavi. ACM Trans. algorithms, 2019], where they gave a kernel of O(k(3/2)) vertices and O(k(5/3)) vertices respectively. In the same paper it was questioned whether these bounds can be (optimally) improved to linear ones. Motivated by this question, we apply the rainbow matching technique and prove that TPT admits an (almost linear) kernel of k(1+ O(1)/root log k) vertices and that I2PP admits a kernel of O(k) vertices.

关键词： Kernelization parameterized algorithms Rainbow matching Packing problems

来源：评论

学校读者我要写书评

暂无评论

New FPT algorithms for Finding the Temporal Hybridization Number for Sets of Phylogenetic Trees

引用

ALGORITHMICA 2022年第7期84卷 2050-2087页

作者： Borst, Sander van Iersel, Leo Jones, Mark Kelk, Steven Ctr Wiskunde & Informat CWI POB 94079 NL-1090 GB Amsterdam Netherlands Delft Univ Technol Delft Inst Appl Math Van Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands Maastricht Univ Dept Data Sci & Knowledge Engn DKE POB 616 NL-6200 MD Maastricht Netherlands

We study the problem of finding a temporal hybridization network containing at most k reticulations, for an input consisting of a set of phylogenetic trees. First, we introduce an FPT algorithm for the problem on an arbitrary set of m binary trees with n leaves each with a running time of O(5(k).n.m). We also present the concept of temporal distance, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most d and at most k reticulations in O((8k)(d)5(k).k.n.m) time. Lastly, we introduce an O(6(k)k!.k.n(2)) time algorithm for computing a temporal hybridization network for a set of two nonbinary trees. We also provide an implementation of all algorithms and an experimental analysis on their performance.

关键词： parameterized algorithms Phylogenetic networks Phylogenetic trees Hybridization number

来源：评论

学校读者我要写书评

暂无评论

Stable Matchings with Restricted Preferences: Structure and Complexity

引用

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2022年第3期10卷 13-13页

作者： Cheng, Christine T. Rosenbaum, Will Univ Wisconsin 3200 N Cramer Ave Milwaukee WI 53211 USA Amherst Coll POB 5000 Amherst MA 01002 USA

In the stable marriage (SM) problem, there are two sets of agents-traditionally referred to as men and women-and each agent has a preference list that ranks (a subset of) agents of the opposite sex. The goal is to find a matching between men and women that is stable in the sense that no man-woman pair mutually prefers each other to their assigned partners. In a seminal work, Gale and Shapley [16] showed that stable matchings always exist and described an efficient algorithm for finding one. Irving and Leather [24] defined the rotation poset of an SM instance and showed that it determines the structure of the set of stable matchings of the instance. They further showed that every finite poset can be realized as the rotation poset of some SM instance. Consequently, many problems-such as counting stable matchings and finding certain "fair" stable matchings-are computationally intractable (NP-hard) in general. In this article, we consider SM instances in which certain restrictions are placed on the preference lists. We show that three natural preference models-k-bounded, k-attribute, and (k(1), k(2))-list-can realize arbitrary rotation posets for constant values of k. Hence, even in these highly restricted preference models, many stable matching problems remain intractable. In contrast, we show that for any fixed constant k, the rotation posets of k-range instances are highly restricted. As a consequence, we show that exactly counting and uniformly sampling stable matchings, finding median, sex-equal, and balanced stable matchings, are fixed-parameter tractable when parameterized by the range of the instance. Thus, these problems can be solved in polynomial time on instances of the k-range model for any fixed constant k.

关键词： Stable matchings restricted preferences parameterized algorithms parameterized complexity rotation poset

来源：评论

学校读者我要写书评

暂无评论

Hamsi-based parametrized family of hash-functions

引用

JOURNAL OF COMPUTER VIROLOGY AND HACKING TECHNIQUES 2022年第1期18卷 11-24页

作者： Ermakov, Kirill Dmitrievich SarFTI NINU MEPHI Dept Radiophys & Elect 6 Dukhova St Sarov 607184 Nizhny Novgorod Russia

In this paper a new family of cryptographic hash-functions is described. The main goal was to create a such hash function, where algorithm varies depending on hash code length. Hash function Hamsi was taken as basis of a parameterized algorithm. This hash function was analyzed in a different ways. For a linear transformation, whole class of linear transformations with the same branch numbers was defined. For this class were found invariant subspaces. The second part of the analysis was a research of differential attacks on Hamsi compression function. After the analysis of published works, changes were made to compression function. With these changes a parameterized hash function Hansi-n was described, that produces n bit of hash code (e.g. 512, 1024, 2048). To find out complexity of different versions of algorithm, the estimation of bitwise operations needed for one compression function evaluation is described. This new hash-functions can be used in a lot of applications, where hash-codes of varying length are needed.

关键词： Cryptographic primitives Hash-functions parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Proportionally Fair Matching with Multiple Groups 1

引用

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

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Inamdar, Tanmay Simonov, Kirill Portland State Univ Portland OR USA Univ Bergen Bergen Norway Univ Potsdam Hasso Plattner Inst Potsdam Germany

ISBN: (数字)9783031433801

ISBN: (纸本)9783031433795;9783031433801

We study matching problems with the notion of proportional fairness. Proportional fairness is one of the most popular notions of group fairness where every group is represented up to an extent proportional to the final selection size. Matching with proportional fairness or more commonly, proportionally fair matching, was introduced in [Chierichetti et al., AISTATS, 2019]. In this problem, we are given a graph G whose edges are colored with colors from a set C. The task is for given 0 <= alpha <= beta <= 1, to find a maximum (alpha, beta)-balanced matching M in G, that is a matching where for every color c is an element of C the number of edges in M of color c is between alpha|M| and beta|M|. Chierichetti et al. initiated the study of this problem with two colors and in the context of bipartite graphs only. However, in many practical applications, the number of colorsalthough often a small constant-is larger than two. In this work, we make the first step towards understanding the computational complexity of proportionally fair matching with more than two colors. We design exact and approximation algorithms achieving reasonable guarantees on the quality of the matching as well as on the time complexity, and our algorithms work in general graphs. Our algorithms are also supported by suitable hardness bounds.

关键词： Matching Fairness parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Interprocedural Data-Flow Analysis Using Treedepth and Treewidth 1

引用

24th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI) part of the 50th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL)

作者： Goharshady, Amir Kafshdar Zaher, Ahmed Khaled Hong Kong Univ Sci & Technol Clear Water Bay Hong Kong Peoples R China

ISBN: (数字)9783031249501

ISBN: (纸本)9783031249495;9783031249501

We consider interprocedural data-flow analysis as formalized by the standard IFDS framework, which can express many widelyused static analyses such as reaching definitions, live variables, and nullpointer. We focus on the well-studied on-demand setting in which queries arrive one-by-one in a stream and each query should be answered as fast as possible. While the classical IFDS algorithm provides a polynomialtime solution for this problem, it is not scalable in practice. More specifically, it will either require a quadratic-time preprocessing phase or takes linear time per query, both of which are untenable for modern huge codebases with hundreds of thousands of lines. Previous works have already shown that parameterizing the problem by the treewidth of the program's control-flow graph is promising and can lead to significant gains in efficiency. Unfortunately, these results were only applicable to the limited special case of same-context queries. In this work, we obtain significant speedups for the general case of on-demand IFDS with queries that are not necessarily same-context. This is achieved by exploiting a new graph sparsity parameter, namely the treedepth of the program's call graph. Our approach is the first to exploit the sparsity of control-flow graphs and call graphs at the same time and parameterize by both the treewidth and the treedepth. We obtain an algorithm with a linear preprocessing phase that can answer each query in constant time wrt the size of the input. Finally, our experimental results demonstrate that our approach significantly outperforms the classical IFDS and its on-demand variant.

关键词： Static analysis Data-flow analysis IFDS parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Turan's Theorem Through Algorithmic Lens 49th

Turan's Theorem Through Algorithmic Lens

引用

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

作者： Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill Univ Bergen Dept Informat Bergen Norway Steklov Inst Math St Petersburg Dept St Petersburg Russia Univ Potsdam Hasso Plattner Inst Potsdam Germany

ISBN: (纸本)9783031433795;9783031433801

The fundamental theorem of Tur ' an from Extremal Graph Theory determines the exact bound on the number of edges t(r)(n) in an n-vertex graph that does not contain a clique of size r + 1. We establish an interesting link between Extremal Graph Theory and algorithms by providing a simple compression algorithm that in linear time reduces the problem of finding a clique of size l in an n-vertex graph G with m >= t(r)(n) - k edges, where l <= r + 1, to the problem of finding a maximum clique in a graph on at most 5k vertices. This also gives us an algorithm deciding in time 2.49(k) center dot (n + m) whether G has a clique of size l. As a byproduct of the new compression algorithm, we give an algorithm that in time 2(O(td2)) center dot n(2) decides whether a graph contains an independent set of size at least n/(d+ 1)+ t. Here d is the average vertex degree of the graph G. The multivariate complexity analysis based on ETH indicates that the asymptotical dependence on several parameters in the running times of our algorithms is tight.

关键词： parameterized algorithms Extremal graph theory Turan's theorem Above guarantee Kernelization Exponential time hypothesis

来源：评论

学校读者我要写书评

暂无评论

Contraction Bidimensionality of Geometric Intersection Graphs

引用

ALGORITHMICA 2022年第2期84卷 510-531页

作者： Baste, Julien Thilikos, Dimitrios M. Univ Lille CRIStAL Cent Lille Lille France Univ Montpellier CNRS LIRMM Montpellier France

Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Gamma(k). A graph class G has the SQGC property if every graph G is an element of G has treewidth O(bcg(G)(c)) for some 1 <= c < 2. The SQGC property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQGC property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.

关键词： Treewidth Bidimensionality parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：