TY - JOUR

T1 - How to pack directed acyclic graphs into small blocks

AU - Asahiro, Yuichi

AU - Furukawa, Tetsuya

AU - Ikegami, Keiichi

AU - Miyano, Eiji

AU - Yagita, Tsuyoshi

N1 - Funding Information:
The authors would like to thank the anonymous reviewers for their constructive comments and suggestions, which helped us to improve the presentation of the paper and design the faster algorithm in Lemma 5 . This work is partially supported by Japan Society for the Promotion of Science (JSPS) KAKENHI Grant Numbers JP17K00016 (E. Miyano), JP17K00024 (Y. Asahiro), and Japan Science and Technology Agency (JST) CREST JPMJCR1402 (E. Miyano, T. Yagita).
Publisher Copyright:
© 2020 Elsevier B.V.

PY - 2021/1/15

Y1 - 2021/1/15

N2 - This paper studies the following variant of clustering or laying out problems for directed acyclic graphs (DAG for short), called the minimum block transfer problem. The objective of this problem is to find a partition of a node set which satisfies the following two conditions: (i) Each element (called a block) of the partition has a size that is at most B and (ii) the maximum number of external arcs among directed paths from the roots to the leaves is minimized. Here, an external arc is defined as an arc connecting two distinct blocks. This paper mainly studies the case B=2. First, we show that the problem is NP-hard even if the height of DAGs is three and its maximum indegree and outdegree are two and three, respectively. Then, we design (i) linear-time optimal algorithms for DAGs of height at most two, (ii) a very simple 2-approximation algorithm, and moreover, (iii) a (2−2∕h)-approximation algorithm for the case that the height h of the input DAG is even and the other one for odd h, whose approximation ratio is 2−2∕(h+1). As for the inapproximability of the problem, for any ε>0 and unless P = NP, we show that the problem does not admit any polynomial time (3∕2−ε)-approximation ((4∕3−ε)-approximation, resp.) algorithm if the height of the input DAGs is restricted to at most five (at least six, resp.). Also, in the case B≥3, we show the NP-hardness and prove a (3∕2−ε)-inapproximability of this case.

AB - This paper studies the following variant of clustering or laying out problems for directed acyclic graphs (DAG for short), called the minimum block transfer problem. The objective of this problem is to find a partition of a node set which satisfies the following two conditions: (i) Each element (called a block) of the partition has a size that is at most B and (ii) the maximum number of external arcs among directed paths from the roots to the leaves is minimized. Here, an external arc is defined as an arc connecting two distinct blocks. This paper mainly studies the case B=2. First, we show that the problem is NP-hard even if the height of DAGs is three and its maximum indegree and outdegree are two and three, respectively. Then, we design (i) linear-time optimal algorithms for DAGs of height at most two, (ii) a very simple 2-approximation algorithm, and moreover, (iii) a (2−2∕h)-approximation algorithm for the case that the height h of the input DAG is even and the other one for odd h, whose approximation ratio is 2−2∕(h+1). As for the inapproximability of the problem, for any ε>0 and unless P = NP, we show that the problem does not admit any polynomial time (3∕2−ε)-approximation ((4∕3−ε)-approximation, resp.) algorithm if the height of the input DAGs is restricted to at most five (at least six, resp.). Also, in the case B≥3, we show the NP-hardness and prove a (3∕2−ε)-inapproximability of this case.

UR - http://www.scopus.com/inward/record.url?scp=85089947887&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089947887&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.08.005

DO - 10.1016/j.dam.2020.08.005

M3 - Article

AN - SCOPUS:85089947887

SN - 0166-218X

VL - 288

SP - 91

EP - 113

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -