Abstract. The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678–708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [ SIAM J. Discrete Math., 30 (2016), pp. 777–800] gave a [Formula: see text]-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in [Formula: see text] time, where [Formula: see text] is the number of nodes, [Formula: see text] is the number of edges, [Formula: see text] is the number of terminals, [Formula: see text] is the maximum edge-cost, [Formula: see text] is the maximum edge-capacity, and [Formula: see text] is the time complexity of a max-flow algorithm in a network with [Formula: see text] nodes and [Formula: see text] edges. The algorithm implies that the [Formula: see text]-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovász–Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem.

Abstract In this paper, we address computation of the degree $$\deg {\rm Det} A$$ deg Det A of Dieudonné determinant $${\rm Det} A$$ Det A of $$\begin{aligned} A = \sum_{k=1}^m A_k x_k t^{c_k}, \end{aligned}$$ A = ∑ k = 1 m A k x k t c k , where $$A_k$$ A k are $$n \times n$$ n × n matrices over a field $$\mathbb{K}$$ K , $$x_k$$ x k are noncommutative variables, t is a variable commuting with $$x_k$$ x k , $$c_k$$ c k are integers, and the degree is considered for t. This problem generalizes noncommutative Edmonds' problem and fundamental combinatorial optimization problems including the weighted linear matroid intersection problem. It was shown that $$\deg {\rm Det} A$$ deg Det A is obtained by a discrete convex optimization on a Euclidean building (Hirai 2019). We extend this framework by incorporating a cost-scaling technique and show that $$\deg {\rm Det} A$$ deg Det A can be computed in time polynomial of $$n,m,\log_2 C$$ n , m , log 2 C , where $$C:= \max_k |c_k|$$ C : = max k | c k | . We give a polyhedral interpretation of $$\deg {\rm Det}$$ deg Det , which says that $$\deg {\rm Det}$$ deg Det A is given by linear optimization over an integral polytope with respect to objective vector $$c = (c_k)$$ c = ( c k ) . Based on it, we show that our algorithm becomes a strongly polynomial one. We also apply our result to an algebraic combinatorial optimization problem arising from a symbolic matrix having $$2 \times 2$$ 2 × 2 -submatrix structure.