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.

Let C be a set of colors, and let ω(c) be an integer cost assigned to a color c in C. An edge-coloring of a graph G is to color all the edges of G so that any two adjacent edges are colored with different colors in C. The cost ω(f) of an edge-coloring f of G is the sum of costs ω(f(e)) of colors f(e) assigned to all edges e in G. An edge-coloring f of G is optimal if ω(f) is minimum among all edge-colorings of G. In this paper, we show that the problem of finding an optimal edge-coloring of a tree T can be simply reduced in polynomial time to the minimum weight perfect matching problem for a new bipartite graph constructed from T. The reduction immediately yields an efficient simple algorithm to find an optimal edge-coloring of T in time O(n1.5Δlog(nNω)), where n is the number of vertices in T, Δ is the maximum degree of T, and Nω is the maximum absolute cost |ω(c)| of colors c in C. We then show that our result can be extended for multitrees.

Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers li and ui, 1 ≤ i ≤ q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 ≤ i ≤ q. The problem of finding such a "uniform" partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees, that is, graphs with bounded tree-width.

Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.

Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by k). The edge-coloring problem is one of the well-known combinatorial problems for which no NC algorithms have been obtained for partial k-trees. This paper gives an optimal and first NC parallel algorithm to find an edge-coloring of any given partial k-tree with bounded degrees using a minimum number of colors. In the paper k is assumed to be bounded.

Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). It is known that any series-parallel simple graph G has an L-edge-coloring if either (i) |L(e)| max{4,d(v),d(w)} for each edge e=vw or (ii) the maximum degree of G is at most three and |L(e)| 3 for each edge e, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. In this paper we give a linear-time algorithm for finding such an L-edge-coloring of a series-parallel graph G.

Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.

Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). In this paper, we prove that any series-parallel simple graph G has an L-edge-coloring if |L(e)| max{3,d(v),d(w)} for each edge e = vw, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. Our proof yields a linear algorithm for finding an L-edge-coloring of series-parallel graphs.

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring for given L. In this paper, we give a sufficient condition for a series-parallel graph to have a list total coloring, and we present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G and L satisfy the sufficient condition.

We study a reconfiguration problem for Steiner trees in an unweighted graph, which determines whether there exists a sequence of Steiner trees that transforms a given Steiner tree into another one by exchanging a single edge at a time. In this paper, we show that the problem is PSPACE-complete even for split graphs, while solvable in linear time for interval graphs and for cographs.

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.

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.

A total coloring of a graph G is to color all vertices and edges of G so that no two adjacent or incident elements receive the same color. Let C be a set of colors, and let ω be a cost function which assigns to each color c in C a real number ω(c) as a cost of c. A total coloring f of G is called an optimal total coloring if the sum of costs ω(f(x)) of colors f(x) assigned to all vertices and edges x is as small as possible. In this paper, we give an algorithm to find an optimal total coloring of any tree T in time O(nΔ3) where n is the number of vertices in T and Δ is the maximum degree of T.

In this paper we newly define a generalized edge-ranking of a graph G as follows: for a positive integer c, a c-edge-ranking of G is a labeling (ranking) of the edges of G with integers such that, for any label i, deletion of all edges with labels >i leaves connected components, each having at most c edges with label i. The problem of finding an optimal c-edge-ranking of G, that is, a c-edge-ranking using the minimum number of ranks, has applications in scheduling the manufacture of complex multi-part products; it is equivalent to finding a c-edge-separator tree of G having the minimum height. We present an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n2log Δ), where n is the number of vertices in T and Δ is the maximum vertex-degree of T. Our algorithm is faster than the best algorithm known for the case c=1.

Millimeter wave (mmWave) massive Multiple-Input Multiple-Output (MIMO) systems generally adopt hybrid precoding combining digital and analog precoder as an alternative to full digital precoding to reduce RF chains and energy consumption. In order to balance the relationship between spectral efficiency, energy efficiency and hardware complexity, the hybrid-connected system structure should be adopted, and then the solution process of hybrid precoding can be simplified by decomposing the total achievable rate into several sub-rates. However, the singular value decomposition (SVD) incurs high complexity in calculating the optimal unconstrained hybrid precoder for each sub-rate. Therefore, this paper proposes PAST, a low complexity hybrid precoding algorithm based on projection approximate subspace tracking. The optimal unconstrained hybrid precoder of each sub-rate is estimated with the PAST algorithm, which avoids the high complexity process of calculating the left and right singular vectors and singular value matrix by SVD. Simulations demonstrate that PAST matches the spectral efficiency of SVD-based hybrid precoding in full-connected (FC), hybrid-connected (HC) and sub-connected (SC) system structure. Moreover, the superiority of PAST over SVD-based hybrid precoding in terms of complexity and increases with the number of transmitting antennas.

To reduce the error of channel estimation caused by noise, a novel noise suppression method based on the degree of confidence is proposed in this paper. The false alarm and false dismissal probabilities, corresponding to noise being taken as part of channel impulse response (CIR) and part of the CIR being mis-detected as noise, respectively, are also investigated. A false alarm reduction method is therefore presented to reduce the false alarms in the estimated CIR while the mis-detection ratio still remains low. Simulation results show the effectiveness of the proposed method.

Let G be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. Suppose that we are given two list edge-colorings f0 and fr of G, and asked whether there exists a sequence of list edge-colorings of G between f0 and fr such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer k ≥ 6 and planar graphs of maximum degree three, but any computational hardness was unknown for the non-list variant in which every edge has the same list of k colors. In this paper, we first improve the known result by proving that, for every integer k ≥ 4, the problem remains PSPACE-complete even for planar graphs of bounded bandwidth and maximum degree three. Since the problem is known to be solvable in polynomial time if k ≤ 3, our result gives a sharp analysis of the complexity status with respect to the number k of colors. We then give the first computational hardness result for the non-list variant: for every integer k ≥ 5, the non-list variant is PSPACE-complete even for planar graphs of bandwidth quadratic in k and maximum degree k.

The energy of a threshold circuit C is defined to be the maximum number of gates outputting ones for an input assignment, where the maximum is taken over all the input assignments. In this paper, we study computational power of threshold circuits of energy at most two. We present several results showing that the computational power of threshold circuits of energy one and the counterpart of energy two are remarkably different. In particular, we give an explicit function which requires an exponential size for threshold circuits of energy one, but is computable by a threshold circuit of size just two and energy two. We also consider MOD functions and Generalized Inner Product functions, and show that these functions also require exponential size for threshold circuits of energy one, but are computable by threshold circuits of substantially less size and energy two.

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 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.