Graph labelings derived from models in distributed computing: A complete complexity classification
Graph labelings derived from models in distributed computing: A complete complexity classification
复制标题
从分布式计算模型派生的图标签：完整的复杂性分类
作者：
Jérémie Chalopin;D. Paulusma
我们讨论了11个已知的分布式计算基本模型：四个消息传递模型，它们不同于(不)端口号的存在，以及七个本地计算模型的层次结构。在每个模型中，我们都研究了当领导者选举时决策问题的计算复杂性，以及命名问题是否能在给定网络上得到解决。已知这两个决策问题对于两个模型在多项式时间内是可解的，而对于另一个模型是协同NP完全的。在这里，我们通过证明它们是co-NP-完全的来解决剩下的八个模型中这两个问题的计算复杂性。我们通过将每个问题转化为图标记问题来实现这一点。利用这一技巧，我们还得到了已知的co-NP完备性结果的另一种证明。在文章的第二部分，我们对所有相应的图标记问题的计算复杂性进行了完全的分类，即对于每个固定的整数$kgeq1$，我们确定了一个给定的图是否允许使用至多k个标记的图标记问题的复杂性。我们还解释了这些标号与满足一些进一步的(全局或局部)约束的图同态的密切关系。这产生了一类新的“约束”图同态，其中包括已知的局部约束图同态。©2011威利期刊公司网络，2011年
We discuss 11 known basic models of distributed computing: four message‐passing models that differ by the (non)existence of port‐numbers and a hierarchy of seven local computations models. In each of these models, we study the computational complexity of the decision problems if the leader election and if the naming problem can be solved on a given network. It is already known that these two decision problems are solvable in polynomial time for two models and are co‐NP‐complete for another one. Here, we settle the computational complexity for both problems in the remaining eight models by showing that they are co‐NP‐complete. We do this by translating each problem into a graph labeling problem. By using this technique, we also obtain an alternative proof for the already known co‐NP‐completeness result. In the second part of our article, we completely classify the computational complexity of all the corresponding graph labeling problems, i.e., for every fixed integer $kgeq 1$ we determine the complexity of the problem that asks whether a given graph allows a certain graph labeling that uses at most k labels. We also explain the close relationship of these labelings to graph homomorphisms that satisfy some further (global or local) constraints. This yields a new class of “constrained” graph homomorphisms that include the already known locally constrained graph homomorphisms. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011
影响因子：
1.1
作者：
Chalopin J
通讯作者：
Chalopin J