Misc

In discrete convex analysis, which is a unified framework of discrete convex functions based on the theory of matroids and submodular functions, efficient discrete optimization algorithms were proposed. In order to disseminate these theoretical results in application fields, we release softwares and web applications implementing algorithms developed in discrete convex analysis.

A bipartite graph is said to be symmetric if it has symmetry of reflecting two vertex sets. This paper investigates matching structure of symmetric bipartite graphs. We first apply the Dulmage-Mendelsohn decomposition to a symmetric bipartite graph. The resulting components, which are matching-covered, turn out to have symmetry. We then decompose a matching-covered bipartite graph via an ear decomposition, which is a sequence of subgraphs obtained by adding an odd-length path repeatedly. We show that, if a matching-covered bipartite graph is symmetric, an ear decomposition can retain symmetry by adding no more than two paths. As an application of these decompositions to combinatorial matrix theory, we present a natural generalization of Polya's problem. We introduce the problem of deciding whether a rectangular matrix has a signing that is totally sign-nonsingular or not, where a rectangular matrix is totally sign-nonsingular if the sign of the determinant of each submatrix with row size is uniquely determined by the signs of the nonzero entries. We show that this problem can be solved in polynomial time with the aid of the matching structure of symmetric bipartite graphs.

We consider the minimum-cost b-edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of this open problem in the following three directions. (1) We give the first combinatorial polynomial-time algorithm for paths. Prior to our work, the polynomial-time algorithm for paths used linear programming, and it was known that the linear-programming approach could not be extended to trees. Thus, our algorithm would yield an alternative approach to a possible polynomial-time algorithm for trees. (2) We give a fixed-parameter algorithm for trees with the number of leaves as a parameter. Thus, a possible NP-hardness proof for trees should make use of trees with unbounded number of leaves. (3) We give a fully polynomial-time approximation scheme for trees. Prior to our work, the best known approximation factor was two. If the problem is NP-hard, then a possible proof cannot be done via a gap-preserving reduction from any APX-hard problem unless P = NP.

This paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of the sign patterns of the solutions is uniquely determined by the sign patterns of the given coefficients. We provide a characterization for sign-solvable LCPs such that the coefficient matrix has nonzero diagonals,which can be tested in polynomial time. This characterization leads to an efficient combinatorial algorithm to find the sign pattern of a solution for these LCPs. The algorithm runs in O(γ) time,where γ is the number of the nonzero coefficients.