同态重构的复杂性

《ACM Transactions on Computation Theory》：The Complexity of Homomorphism Reconstructibility

同态可重构性问题研究，揭示其在NP^#P-困难性及参数化复杂性。摘要：同态计数在数据库和机器学习中具有应用潜力，研究其可重构性问题。证明该问题NP^#P-困难，当输入图集有限或图阶受限时，问题NP-困难。对单图及多图子图计数情形获得fpt算法。

　　

摘要

近年来，通过图的同态计数来表示图的方法催生了“同态不可区分性”这一美丽的理论。此外，同态计数在数据库理论和机器学习领域也有广泛应用，在这些领域中，人们希望仅根据图 G 作为从某些固定有限图集到 G 的同态计数的有限向量表示来回答问题或对图进行分类。我们研究了与这些表示相关的一个最基本的计算问题的计算复杂性，即“同态重构问题”：给定一系列图和一个相应的自然数向量，判断是否存在一个图 G，使得该图能够实现给定的向量，即作为这些图的同态计数结果。

我们证明了这个问题是一个典型的 NP^#P 难问题；即使将其限制在输入图的树宽有界且输入的自然数向量固定的情况下，或者限制在输入图集有限的情况下，它仍然可能是 NP 难问题。进一步地，我们还发现，当问题限制在输入图集有限的情况下，并且给定图 G 的阶数的上限作为额外输入时，除非 P = NP，否则该问题不可能是 NP 难问题。对于这种情况，我们取得了一些部分积极的结果。我们还研究了该问题的参数化复杂性，并为给定单个图的情况以及给定多个相同阶数的图（这些图以子图的形式提供而非同态计数的情况）提供了多项式时间（fpt）算法。