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.

In this paper, we address the problem of finding a representation of a subtree distance, which is an extension of a tree metric. We show that a minimal representation is uniquely determined by a given subtree distance, and give an O(n2) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Ω(n2), our algorithm achieves the optimal time complexity.

For a graph G=(V,E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n2) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where smax is the size of maximum matching. This is the first exact maximum matching algorithm in o(n2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(smax) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.

Due to most of the existing graph repartitioning methods are known for poor efficiency in distributed environments. In this paper, we introduce a new graph repartitioning method with two phases in distributed environments. In the first phase, a local method is designed to identify all the potential candidate vertices that should be moved to the other partitions at once in each partition locally. In the second phase, a streaming graph processing model is adopted to reassign the candidate vertices to achieve lightweight graph repartitioning. During the reassignment of the vertex, we propose an objective function to balance both the load balance and the number of crossing edges among the distributed partitions. The experimental results with a large set of real word and synthetic graph datasets show that the communication cost can be reduced by nearly 1 to 2 orders of magnitude compared with the existing methods.

In this article, we propose a method to identify the link layer home network topology, motivated by applications to cost reduction of support centers. If the topology of home networks can be identified automatically and efficiently, it is easier for operators of support centers to identify fault points. We use MAC address forwarding tables (AFTs) which can be collected from network devices. There are a couple of existing methods for identifying a network topology using AFTs, but they are insufficient for our purpose; they are not applicable to some specific network topologies that are typical in home networks. The advantage of our method is that it can handle such topologies. We also implemented these three methods and compared their running times. The result showed that, despite its wide applicability, our method is the fastest among the three.

We study the problem of transforming one (vertex) c-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a c-coloring, where c denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant c ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if c is a fixed constant. We then demonstrate that, even when c is a part of input, the problem is solvable in polynomial time for several graph classes, such as k-trees with any integer k ≥ 1, split graphs, and trivially perfect graphs.

This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.

Discrete structure manipulation is a fundamental technique for many problems solved by computers. BDDs/ZDDs have attracted a great deal of attention for twenty years, because those data structures are useful to efficiently manipulate basic discrete structures such as logic functions and sets of combinations. Recently, one of the most interesting research topics related to BDDs/ZDDs is Frontier-based search method, a very efficient algorithm for enumerating and indexing the subsets of a graph to satisfy a given constraint. This work is important because many kinds of practical problems can be efficiently solved by some variations of this algorithm. In this article, we present recent research activity related to BDD and ZDD. We first briefly explain the basic techniques for BDD/ZDD manipulation, and then we present several examples of the state-of-the-art algorithms to show the power of enumeration.

Suppose that we are given two vertex covers C0 and Ct of a graph G, together with an integer threshold k ≥ max{|C0|, |Ct|}. Then, the vertex cover reconfiguration problem is to determine whether there exists a sequence of vertex covers of G which transforms C0 into Ct such that each vertex cover in the sequence is of cardinality at most k and is obtained from the previous one by either adding or deleting exactly one vertex. This problem is PSPACE-complete even for planar graphs. In this paper, we first give a linear-time algorithm to solve the problem for even-hole-free graphs, which include several well-known graphs, such as trees, interval graphs and chordal graphs. We then give an upper bound on k for which any pair of vertex covers in a graph G has a desired sequence. Our upper bound is best possible in some sense.

We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives sharp analyses of the problem with respect to pathwidth.

A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.

Suppose that each arc in a digraph D = (V,A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard for any fixed constant number of terminals with |K| ≥ 3, while it is solvable in polynomial time for at most two terminals. We also give an inapproximability result for any fixed constant number of terminals with |K| ≥ 3. Finally, we give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|), and the hidden constant factor of the running time is just a single exponential of the treewidth.

By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA'11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al.'s algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.

This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly n vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3],[6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all “ordered” trees with n vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with n vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k=1,2, ...,n-1, we can also generate all rooted trees with exactly n vertices.

We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing only one edge color assignment at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. Ito, Kamiski and Demaine gave a sufficient condition so that any list edge-coloring of a tree can be transformed into any other. In this paper, we give a new sufficient condition which improves the known one. Our sufficient condition is best possible in some sense. The proof is constructive, and yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices via O(n2) recoloring steps. We remark that the upper bound O(n2) on the number of recoloring steps is tight, because there is an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Ω(n2) recoloring steps.

In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.

In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers n ≥ 3 and g ≥ 3, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly n vertices such that the size of each inner face is at most g without delivering two symmetric copies of the same graph.

We consider the minimum cost edge installation problem (MCEI) in a graph G=(V,E) with edge weight w(e)≥ 0, e∈ E. We are given a vertex s∈ V designated as a sink, an edge capacity λ>0, and a source set S⊆ V with demand q(v)∈ [0,λ], v∈ S. For each edge e∈ E, we are allowed to install an integer number h(e) of copies of e. MCEI asks to send demand q(v) from each source v∈ S along a single path Pv to the sink s without splitting the demand of any source v∈ S. For each edge e∈ E, a set of such paths can pass through a single copy of e in G as long as the total demand along the paths does not exceed the edge capacity λ. The objective is to find a set P={Pv| v∈ S∈ of paths of G that minimizes the installing cost ∑e∈ E h(e)w(e). In this paper, we propose a (15/8+ρST)-approximation algorithm to MCEI, where ρST is any approximation ratio achievable for the Steiner tree problem.

The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.

We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G=(V,E) with a vertex set V, an edge set E and an edge weight w(e) ≥ 0, e ∈ E. We are given a source set S ⊆ V with a weight g(e) ≥ 0, e ∈ S, a terminal set M ⊆ V-S with a demand function q : M → R+, and a real number κ > 0, where g(s) means the cost for opening a vertex s ∈ S as a source in a multicast tree. Then the CMMTR asks to find a subset S′⊆ S, a partition {Z1,Z2,...,Zl} of M, and a set of subtrees T1,T2,...,Tl of G such that, for each i, ∑t∈Ziq(t) ≤ κ and Ti spans Zi∪{s} for some s ∈ S′. The objective is to minimize the sum of the opening cost of S′and the constructing cost of {Ti}, i.e., ∑s∈S′g(s)+w(Ti), where w(Ti) denotes the sum of weights of all edges in Ti. In this paper, we propose a (2ρUFL+ρST)-approximation algorithm to the CMMTR, where ρUFL and ρST are any approximation ratios achievable for the uncapacitated facility location and the Steiner tree problems, respectively. When all terminals have unit demands, we give a ((3/2)ρUFL+(4/3)ρST)-approximation algorithm.