PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n ~(8))time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n ~(4)(n +m )) time algorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage. Since each graph of the input has n -1 vertices and O(n ~(2)) edges, the input size is O(n ~(3)) (, or O(nm )). There are polynomial time isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.
展开▼
机译:Kratsch和Hemaspaandra的PREIMAGE CONSTRUCTION问题自然是由著名的图重构猜想引起的。它涉及猜想的算法方面。我们提出了一种在置换图上用于PREIMAGE构造的O( n〜(8))时间算法和一种用于PREIMAGE的O( n〜(4)( n + m))时间算法构造距离遗传图,其中 n是输入中图的数目, m是原像中的边数。由于输入的每个图都有 n -1个顶点和O( n〜(2))个边,因此输入大小为O( n〜(3))(或O( nm))。对于置换图和距离遗传图,有多项式时间同构算法。但是,通过将顶点添加到置换(距离-遗传)图而获得的置换(距离-遗传)图的数量通常成倍增加。因此,这些图的详尽检查无法实现任何多项式时间算法。因此,减少原像候选的数量是关键。
展开▼