IEICE TRANSACTIONS on Information
DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks
Summary :
This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E106-D No.3 pp.272-283
- Publication Date
- 2023/03/01
- Publicized
- 2022/12/22
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2022FCP0007
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — Foundations of Computer Science Supporting the Information Society —)
- Category
Authors
Shoji KASAHARA
Nara Institute of Science and Technology
Jun KAWAHARA
Kyoto University
Shin-ichi MINATO
Kyoto University
Jumpei MORI
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shoji KASAHARA, Jun KAWAHARA, Shin-ichi MINATO, Jumpei MORI, "DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 3, pp. 272-283, March 2023, doi: 10.1587/transinf.2022FCP0007.
Abstract: This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022FCP0007/_p
Copy
@ARTICLE{e106-d_3_272,
author={Shoji KASAHARA, Jun KAWAHARA, Shin-ichi MINATO, Jumpei MORI, },
journal={IEICE TRANSACTIONS on Information},
title={DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks},
year={2023},
volume={E106-D},
number={3},
pages={272-283},
abstract={This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint 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={},
doi={10.1587/transinf.2022FCP0007},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks
T2 - IEICE TRANSACTIONS on Information
SP - 272
EP - 283
AU - Shoji KASAHARA
AU - Jun KAWAHARA
AU - Shin-ichi MINATO
AU - Jumpei MORI
PY - 2023
DO - 10.1587/transinf.2022FCP0007
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2023
AB - This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint 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.
ER -
English
