AF: Small: Algorithms meet Structural Graph Decomposition

AF：小：算法满足结构图分解

• 批准号: 2008838
• 负责人: Daniel Lokshtanov
• 金额: $ 34.99万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008838&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; meet; Structural

A graph consists of dots, called vertices, representing objects, and lines between these dots, called edges, representing relationships between the objects the edge connects. Graphs and graph algorithms have a crucial role in computing, and by extension in all of science. They are used to model such diverse objects as people and friendships (social networks such as Facebook or LinkedIn), maps (Google Maps), connections between neurons in the brain, or the possible configurations of pieces on a chess-board connected by valid moves of chess pieces. For this reason graphs are extensively studied, both from structural and computational viewpoints. The structural approach to graphs often seeks to explain what a graph has to "look like" when it has certain desirable properties. The computational viewpoint seeks to design algorithms (efficient computer programs) that can process a graph to answer questions about it. For example, what is the shortest path from one place (vertex) to another? Which person on this social network is the "most influential?", etc. The aim of this project is a closer connection between the computational and the structural approaches to graphs. Such a connection already exists - for example many graph algorithms are based on powerful structural graph decompositions. However, the usage of structure decompositions in algorithms is most commonly in a black-box fashion - the algorithms simply exploit the structure provided by the theorems. Because the structure theorems were not designed with these concrete algorithmic applications in mind, the obtained algorithms have sub-optimal performance. For other important algorithmic problems the existing structure theorems seem to “not quite fit”, leaving efficient algorithms for these problems just out of reach. In this project the team of researchers will prove new algorithmically-focused graph-structure theorems, and use the new structure theorems to design efficient algorithms.The investigator has identified several directions where algorithmically-minded structure theorems have a big potential for success: graph isomorphism on minor-free graphs, optimization problems on weighted graphs, and (generalized) cut and separation problems. In each of these directions the team of researchers will design radically new algorithms with superior performance guarantees, and take the field far beyond the state of the art. The project cuts to the heart of several well-known open problems in theoretical computer science, specifically within the fields of parameterized algorithms and approximation algorithms. Is there a polynomial time for graph isomprohism if the input graphs exclude a clique with log log(n) vertices as a minor? What is the best approximation algorithm for deleting the fewest possible vertices to get a planar graph? Can approximation schemes for unweighted problems on planar graphs be lifted to their weighted counterparts? What is the parameterized complexity of removing k vertices of minimum weight from a digraph to make it acyclic? This project is to resolve these problems by designing new and algorithmically efficient graph-decomposition theorems. The new decomposition theorems will be built on completely new insights, as well novel combinations of insights from structural graph theory and algorithms. The combination of graph-theoretic and algorithmic thinking holds a wealth of untapped potential. Therefore the results of this project will yield substantial new results both in algorithms and in structural graph theory, and will bring the two fields closer together.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

图形由点（称为顶点）和点之间的线（称为边）组成，点表示对象，点之间的线表示边缘连接的对象之间的关系。图和图算法在计算中起着至关重要的作用，并延伸到所有科学中。它们被用来模拟各种各样的对象，比如人和友谊（Facebook或LinkedIn等社交网络）、地图（谷歌maps）、大脑神经元之间的连接，或者通过棋子的有效移动来连接棋盘上棋子的可能配置。因此，从结构和计算的角度对图进行了广泛的研究。图的结构方法通常试图解释当图具有某些理想属性时它必须“看起来像”什么。计算观点寻求设计算法（高效的计算机程序），可以处理图形来回答有关它的问题。例如，从一个地方（顶点）到另一个地方（顶点）的最短路径是什么？在这个社交网络上，哪个人是“最有影响力的？”等等。这个项目的目的是在图的计算方法和结构方法之间建立更紧密的联系。这种联系已经存在——例如，许多图算法都是基于强大的结构图分解。然而，在算法中使用结构分解最常见的是一种黑盒方式——算法只是利用定理提供的结构。由于在设计结构定理时没有考虑到这些具体的算法应用，所得到的算法具有次优性能。对于其他重要的算法问题，现有的结构定理似乎“不太适合”，使得这些问题的有效算法遥不可及。在这个项目中，研究人员团队将证明新的以算法为中心的图结构定理，并使用新的结构定理来设计高效的算法。研究者已经确定了几个方向，其中算法思想结构定理有很大的成功潜力：图同构在次要无图，优化问题在加权图，和（广义）切割和分离问题。在这些方向中，研究团队将设计出具有卓越性能保证的全新算法，并使该领域远远超出目前的技术水平。该项目触及了理论计算机科学中几个众所周知的开放问题的核心，特别是在参数化算法和近似算法领域。如果输入图排除了一个具有log log(n)个顶点的团，那么图的等差性是否存在多项式时间？什么是最好的近似算法删除最少可能的顶点得到一个平面图？平面图上未加权问题的近似方案是否可以提升到它们的加权对应物？从有向图中移除k个最小权值的顶点，使其成为无环的参数化复杂度是多少？本项目旨在通过设计新的算法高效的图分解定理来解决这些问题。新的分解定理将建立在全新的见解上，以及结构图论和算法见解的新颖组合。图论和算法思维的结合拥有大量未开发的潜力。因此，这个项目的结果将在算法和结构图论方面产生实质性的新结果，并将使这两个领域更加紧密地联系在一起。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Diversity in Kemeny Rank Aggregation: A Parameterized Approach

Kemeny 排名聚合的多样性：参数化方法

• DOI: 10.24963/ijcai.2021/2
• 发表时间: 2021
• 期刊: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
• 作者: Arrighi, Emmanuel;Fernau, Henning;Lokshtanov, Daniel;de Oliveira Oliveira, Mateus;Wolf, Petra
• 通讯作者: Wolf, Petra

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

论连通支配集重构的参数化复杂性

• DOI: 10.1007/s00453-021-00909-5
• 发表时间: 2022
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Lokshtanov, Daniel;Mouawad, Amer E.;Panolan, Fahad;Siebertz, Sebastian
• 通讯作者: Siebertz, Sebastian

Exploiting Dense Structures in Parameterized Complexity

在参数化复杂性中利用密集结构

• 发表时间: 2021
• 期刊: Leibniz international proceedings in informatics
• 作者: Lochet, William;Lokshtanov, Daniel;Saurabh, Saket;Zehavi, Meirav
• 通讯作者: Zehavi, Meirav

A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane

用于导航通过平面内相连障碍物的常数因子近似

• 发表时间: 2021
• 期刊: Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Kumar, Neeraj;Lokshtanov, Daniel;Saurabh, Saket;Suri, Subhash
• 通讯作者: Suri, Subhash

b-Coloring Parameterized by Clique-Width

• DOI: 10.4230/lipics.stacs.2021.43
• 发表时间: 2020-03
• 作者: L. Jaffke;Paloma T. Lima;D. Lokshtanov