DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks

【Author】 Kasahara, Shoji; Kawahara, Jun; Minato, Shin-ichi; Mori, Jumpei

【Source】IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS

【影响因子】0.695

【Abstract】This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the view-point of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.

【Keywords】graph algorithm; computational complexity; directed acyclic graph; pathwidth; blockchain

【发表时间】2023 MAR

【收录时间】2023-04-09

【文献类型】

【主题类别】

--