The Science of Solving Hard Subgraph Problems

解决困难子图问题的科学

• 批准号: EP/X030032/1
• 负责人: Ciaran McCreesh
• 金额: $ 45.98万
• 依托单位: University of Glasgow
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX030032%2F1
• 关键词: Science; Solving; Hard; Subgraph; Problems

Subgraph-finding problems involve identifying patterns in structured data. In theory these problems should be computationally hard for an algorithm to solve, but in practice intelligent constraint-based algorithms can quickly solve even large problems. This research will uses scientific (rather than purely mathematical) techniques to increase our understanding of this gap between theory and practice, and will allow us to design better algorithms in the future. The research is based upon analysing proof logs, which are a mathematical description of how an algorithm reached its answer.

子图发现问题涉及识别结构化数据中的模式。从理论上讲，这些问题在计算上应该很难解决，但是实际上，基于智能约束的算法也可以迅速解决大问题。这项研究将使用科学（而不是纯粹的数学）技术来增加我们对理论和实践之间这种差距的理解，并使我们将来可以设计更好的算法。该研究基于分析证明日志，这是算法如何达到答案的数学描述。