Published papers

Cooperative matching games have drawn much interest partly because of the connection with bargaining solutions in the networking environment. However, it is not always guaranteed that a network under investigation gives rise to a stable bargaining outcome. To address this issue, we consider a modification process, called stabilization, that yields a network with stable outcomes, where the modification should be as small as possible. Therefore, the problem is cast to a combinatorial-optimization problem in a graph. Recently, the stabilization by edge removal was shown to be NP-hard. On the contrary, in this paper, we show that other possible ways of stabilization, namely, edge addition, vertex removal and vertex addition, are all polynomial-time solvable. Thus, we obtain a complete complexity-theoretic classification of the natural four variants of the network stabilization problem. We further study weighted variants and prove that the variants for edge addition and vertex removal are NP-hard. (C) 2017 Elsevier B.V. All rights reserved.

This paper is an attempt to provide a connection between qualitative matrix theory and linear programming. A linear program max{cx vertical bar Ax = b, x >= 0} is said to be sign-solvable if the set of sign patterns of the optimal solutions is uniquely determined by the sign patterns of A, b, and c. It turns out to be NP-hard to decide whether a given linear program is sign-solvable or not. We then introduce a class of sign-solvable linear programs in terms of totally sign-nonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the sign patterns of A, b, and c. The algorithm runs in O(m gamma) time, where m is the number of rows of A and gamma is the number of all nonzero entries in A, b, and c.

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(gamma) time, where gamma is the number of the nonzero coefficients.

A symmetric matrix A is said to be sign-nonsingular if every symmetric matrix with the same sign pattern as A is nonsingular. Hall, Li and Wang showed that the inertia of a sign-nonsingular symmetric matrix is determined uniquely by its sign pattern. The purpose of this paper is to present an efficient algorithm for computing the inertia of such matrices. The algorithm runs in O(nm) time for a symmetric matrix of order n with m nonzero entries. The correctness of the algorithm provides an alternative proof of the result by Hall et al. In addition, for a symmetric matrix in general, it is shown to be NP-complete to decide whether the inertia of the matrix is not determined by the sign pattern.

Given an undirected graph G = (V, E) and a delta-matroid (V, F), the delta-matroid matching problem is to find a maximum cardinality matching M such that the set of the end vertices of M belongs to F. This problem is a natural generalization of the matroid matching problem to delta-matroids, and thus it cannot be solved in polynomial time in general. This paper introduces a class of the delta-matroid matching problem, where the given delta-matroid is a projection of a linear delta-matroid. We first show that it can be solved in polynomial time if the given linear delta-matroid is generic. This result enlarges a polynomially solvable class of matching problems with precedence constraints on vertices such as the 2-master/slave matching. In addition, we design a polynomial-time algorithm when the graph is bipartite and the delta-matroid is defined on one vertex side. This result is extended to the case where a linear matroid constraint is additionally imposed on the other vertex side.

An independence system F is one of the most fundamental combinatorial concepts, which includes a variety of objects in graphs and hypergraphs such as matchings, stable sets, and matroids. We discuss the robustness for independence systems, which is a natural generalization of the greedy property of matroids. For a real number alpha > 0, a set X is an element of F is said to be alpha-robust if for any k, it includes an alpha-approximation of the maximum k-independent set, where a set Y in F is called k-independent if the size vertical bar Y vertical bar is at most k. In this paper, we show that every independence system has a 1/root mu(F)-robust independent set, where mu(F) denotes the exchangeability of F. Our result contains a classical result for matroids and the ones of Hassin and Rubinstein [12] for matchings and Fujita, Kobayashi, and Makino [7] for matroid 2-intersections, and provides better bounds for the robustness for many independence systems such as b-matchings, hypergraph matchings, matroid p-intersections, and unions of vertex disjoint paths. Furthermore, we provide bounds of the robustness for nonlinear weight functions such as submodular and convex quadratic functions. We also extend our results to independence systems in the integral lattice with separable concave weight functions.

In this paper, we study the robustness over the cardinality variation for the knapsack problem. For the knapsack problem and a. positive number alpha <= 1, we say that a feasible solution is alpha-robust if, for any positive integer k, it includes an alpha-approximation of the maximum k-knapsack solution, where a k-knapsack solution is a feasible solution that consists of at most k items. In this paper, we show that, for any epsilon > 0, the problem of deciding whether the knapsack problem admits a (nu+epsilon)-robust solution is weakly NP-hard, where nu denotes the rank quotient of the corresponding knapsack system. Since the knapsack problem always admits a nu-robust knapsack solution [7], this result provides a sharp border for the complexity of the robust knapsack problem. On the positive side, we show that a max-robust knapsack solution can be computed in pseudo-polynomial time, and present a fully polynomial time approximation scheme (FPTAS) for computing a max-robust knapsack solution.

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 (0, 1)-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 the entire row set 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. In addition, we provide a characterization of this problem in terms of excluded minors. (C) 2010 Elsevier Inc. All rights reserved.

Agler, Helton, McCullough, and Rodman proved that a graph is chordal if and only if any positive semidefinite (PSD) symmetric matrix, whose nonzero entries are specified by a given graph, can be decomposed as a sum of PSD matrices corresponding to the maximal cliques. This decomposition is recently exploited to solve positive semidefinite programming efficiently. Their proof is based on a characterization for PSD matrix completion of a chordal-structured matrix due to Grone, Johnson, SS, and Wolkowicz. This note gives a direct and simpler proof for the result of Agler et al., which leads to an alternative proof of Grone et al. (C) 2010 Elsevier Inc. All rights reserved.

© 2018, Springer Science+Business Media, LLC, part of Springer Nature. Consider a graph such that each vertex has a nonnegative integer capacity and each edge has a positive integer weight. Then, a b-matching in the graph is a multi-set of edges (represented by an integer vector on edges) such that the total number of edges incident to each vertex is at most the capacity of the vertex. In this paper, we study a reconfiguration variant for maximum-weight b-matchings: For two given maximum-weight b-matchings in a graph, we are asked to determine whether there exists a sequence of maximum-weight b-matchings in the graph between them, with subsequent b-matchings obtained by removing one edge and adding another. We show that this reconfiguration problem is solvable in polynomial time for instances with no integrality gap. Such instances include bipartite graphs with any capacity function on vertices, and 2-matchings in general graphs. Thus, our result implies that the reconfiguration problem for maximum-weight matchings can be solved in polynomial time for bipartite graphs.

© Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, and Alexandra Kolla. The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of finding symmetric signings of matrices with natural spectral properties. Our results are the following: 1. We characterize matrices that have an invertible signing: a symmetric matrix has an invertible symmetric signing if and only if the support graph of the matrix contains a perfect 2-matching. Further, we present an efficient algorithm to search for an invertible symmetric signing. 2. We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing. 3. We show NP-completeness of the following problems: verifying whether a given matrix has a symmetric signing that is singular or has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs. We use combinatorial techniques in addition to classic results from matching theory.