Published papers

In this paper, we consider the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i.e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.

© 2018 Elsevier Inc. A graph H is immersed in a graph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. In this paper, we show that the Erdős–Pósa property holds for packing edge-disjoint Kt-immersions in 4-edge-connected graphs. More precisely, for positive integers k and t, there exists a constant f(k,t) such that a 4-edge-connected graph G has either k edge-disjoint Kt-immersions, or an edge subset F of size at most f(k,t) such that G−F has no Kt-immersion. The 4-edge-connectivity in this statement is best possible in the sense that 3-edge-connected graphs do not have the Erdős–Pósa property.

A seminal result of Reed et al. [Combinatorica, 16 (1996), pp. 535-554] says that a directed graph has either k vertex-disjoint directed circuits or a set of at most f(k) vertices meeting all directed circuits. This paper aims at generalizing their result to packing directed circuits through a prescribed set S of vertices. Such a circuit is called an S-circuit. Even et al. [Algorithmica, 20 (1998), pp. 151-174] showed a fractional version of packing S-circuits. In this paper, we show that the fractionality can be bounded by at most one-fifth: Given an integer k and a vertex subset S, whose size may not depend on k, we prove that either G has a 1/5-integral packing of k disjoint S-circuits, i.e., each vertex appears in at most five of these S-circuits, or G has a vertex set X of order at most f(k) (for some function f of k) such that G - X has no such circuit. We also give a fixed-parameter tractable approximation algorithm for finding a 1/5-integral packing of S-circuits. This algorithm finds a 1/5-integral packing of size approximately k in polynomial time if it has a 1/5-integral packing of size k for a given directed graph and an integer k.

The well-known theorem of Erdos-Posa says that either a graph G has k disjoint cycles or there is a vertex set X of order at most f (k) for some function f such that G \ X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we present a common generalization of the following Erdos-Posa properties: 1. The Erdos-Posa property for cycles of length divisible by a fixed integer p (Thomassen, 1988 [19]). 2. The Erdos-Posa property for S-cycles, i.e., cycles which contain a vertex of a prescribed vertex set S (Kakimura, Kawarabayashi, and Marx, 2011 [10] and Pontecorvi and Wollan, 2010 [13]). Namely, given integers k. p, and a vertex set S (whose size may not depend on k and p), we prove that either a graph G has k disjoint S-cycles, each of which has length divisible by p, or G has a vertex set X of order at most f (k. p) such that G \ X has no such a cycle. (c) 2012 Elsevier Inc. All rights reserved.

The well-known theorem of Erdos and Posa says that a graph G has either k vertex-disjoint cycles or a vertex set X of order at most f (k) such that G\ X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we generalize Erclos-Posa's result to cycles that are required to go through a set S of vertices. Given an integer k and a vertex subset S (possibly unbounded number of vertices) in a given graph G, we prove that either G has k vertex-disjoint cycles, each of which contains at least one vertex of S. or G has a vertex set X of order at most f (k) = 40k(2) log(2)(k) such that G\ X has no cycle that intersects S. (C) 2011 Elsevier Inc. All rights reserved.

In this paper, we show the Erdos-Pósa property for edge-disjoint packing of S-closed walks with parity constraints in 4-edge-connected graphs. More precisely, we prove that for any 4-edge-connected graph G and any vertex subset S, either G has k edge-disjoint elementary closed odd walks, each of which has at least one vertex of S, or G has an edge set F with |F| ≥ f(k) such that G - F has no such walks. The 4-edge-connectivity is the best possible in the sense that 3-edge-connected graphs do not satisfy the statement. Since the proof is constructive, we can design a fixed-parameter algorithm for finding k edge-disjoint walks satisfying the conditions in a 4-edge-connected graph for a parameter k. In addition, this gives a simple fixed-parameter algorithm for the parity edge-disjoint walks problem with k terminal pairs.

In this paper, we study the parameterized complexity of the linear complementarity problem (LCP), which is one of the most fundamental mathematical optimization problems. The parameters we focus on are the sparsities of the input and the output of the LCP: the maximum numbers of nonzero entries per row/column in the coefficient matrix and the number of nonzero entries in a solution. Our main result is to present a fixed-parameter algorithm for the LCP with all the parameters. We also show that if we drop any of the three parameters, then the LCP is fixed-parameter intractable. In addition, we discuss the nonexistence of a polynomial kernel for the LCP.

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.

The well-known theorem of ErdAs-Psa says that a graph G has either k disjoint cycles or a vertex set X of order at most f(k) for some function f such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we discuss packing disjoint S-cycles, i.e., cycles that are required to go through a set S of vertices. For this problem, Kakimura-Kawarabayashi-Marx (2011) and Pontecorvi-Wollan (2010) recently showed the ErdAs-Psa-type result holds. We further try to generalize this result to packing S-cycles of odd length. In contrast to packing S-cycles, the ErdAs-Psa-type result does not hold for packing odd S-cycles. We then relax packing odd S-cycles to half-integral packing, and show the ErdAs-Psa-type result for the half-integral packing of odd S-cycles, which is a generalization of Reed (1999) when S=V. That is, we show that given an integer k and a vertex set S, a graph G has either 2k odd S-cycles so that each vertex is in at most two of these cycles, or a vertex set X of order at most f(k) (for some function f) such that G\X has no odd S-cycle.

The subset feedback set problem, which is a generalization of the well-known feedback vertex set problem, is that we are given an undirected graph G with a vertex subset S and a positive integer k, and the goal is to find a vertex set X of size at most k such that G - X has no S-cycle, where an S-cycle is a cycle having at least one vertex of S. It was recently shown that this problem is fixed parameter tractable, where k is the parameter. In this paper, we further generalize this problem to one with the parity constraints, and show the fixed parameter tractability: 1. For a parameter k, there exists a fixed-parameter algorithm that either finds a vertex set X of size k such that G - X has no S-cycle of even length, or concludes that such a vertex set does not exist. 2. For a parameter k, there exists a fixed-parameter algorithm that either finds a vertex set X of size k such that G - X has no S-cycle of odd length, or concludes that such a vertex set does not exist. (C) 2015 Elsevier B.V. All rights reserved.

© 2018 Elsevier Inc. Scheduling sensors to prolong the lifetime of target coverage is one of the central problems faced in wireless sensor networks. This problem, called the maximum lifetime coverage problem (MLCP), can be formulated as a linear program with exponential size and has a polynomial-time approximation scheme (PTAS). In reality, however, sensor batteries are subject to the recovery effect, which means that the deliverable energy in a battery can replenish itself if it is left idle for a sufficient duration. Thanks to this effect, we can obtain much longer sensor lifetime if each sensor is intermittently forced to turn off for some interval. In this study, we introduce two models that extend the MLCP to incorporate the battery recovery effect. The first model, called as duty cycle model, represents the battery recovery effect in a deterministic way. The second one, called as linear recovery model, uses a probabilistic model to imitate this effect. We propose two efficient algorithms that work for both models, adapting greedy and Garg–Könemann-based algorithms for the original MLCP. In our numerical experiments, our greedy algorithm performs best in the duty cycle model, while our Garg–Könemann-based algorithm performs best in the linear recovery model. For each network, we compare the longest lifetime obtained from our algorithms with the longest lifetime obtained from algorithms for the original MLCP. As a result, we found that our lifetime is 10–40% longer.

A graph H is immersed in a graph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. The notion of an immersion is quite similar to the well-known notion of a minor, as structural approach inspired by the theory of graph minors has been extremely successful in immersions. Hadwiger's conjecture on graph coloring, generalizing the Four Color Theorem, states that every loopless graph without a K-k-minor is (k - 1)-colorable, where K-k is the complete graph on k vertices. This is a long standing open problem in graph theory, and it is even unknown whether it is possible to determine ck-colorability of K-k-minor-free graphs in polynomial time for some constant c. In this paper, we address coloring graphs without H-immersion. In contrast to coloring H-minor-free graphs, we show the following: 1. there exists a fixed-parameter algorithm to decide whether or not a given graph G without an immersion of a graph H of maximum degree d is (d - 1)-colorable, where the size of H is a parameter. In fact, if G is (d - 1)-colorable, the algorithm produces such a coloring, and 2. for any positive integer k (k >= 6), it is NP-complete to decide whether or not a given graph G without a K-k-immersion is (k - 3)-colorable. (C) 2016 Elsevier Inc. All rights reserved.

In this paper, we discuss generating a matrix *-algebra over the real field with a set of symmetric matrices. This is motivated by an application in structural engineering. We show that any matrix *-algebra can be generated with at most four randomly-chosen symmetric matrices. The proof relies on the structure theorem for matrix *-algebras and the notion of genericity in eigenvalue structure. (C) 2012 Elsevier Inc. All rights reserved.

Deploying caches on a network is an effective way to reduce the amount of data transmitted in a network. Recently, in an academic backbone network such as SINET (the Science Information Network) in Japan, the amount of transmitted data has significantly increased. It is desired to design an efficient mechanism to allocate caches in an optimal way. In this paper, we begin by formulating a discrete optimization model to find a cache allocation that minimizes the total transmission cost. We then design two efficient algorithms to solve our proposed model. The first one makes use of the fact that a backbone network has small treewidth. The algorithm runs in polynomial time when the number of items is fixed and a graph has a bounded treewidth. The other one reduces the problem to the minimum-cost flow problem under the practical assumption that each item has at most one copy. This yields a polynomial-time combinatorial algorithm. Our numerical experiments on the real SINET network show that our algorithms can solve the cache placement problem efficiently in practice.

© 2018, Springer Science+Business Media, LLC, part of Springer Nature. In this paper, we introduce total dual integrality of the linear complementarity problem (LCP) by analogy with the linear programming problem. The main idea of defining the notion is to propose the LCP with orientation, a variant of the LCP whose feasible complementary cones are specified by an additional input vector. Then we naturally define the dual problem of the LCP with orientation and total dual integrality of the LCP. We show that if the LCP is totally dual integral, then all basic solutions are integral. If the input matrix is sufficient or rank-symmetric, and the LCP is totally dual integral, then our result implies that the LCP always has an integral solution whenever it has a solution. We also introduce a class of matrices such that any LCP instance having the matrix as a coefficient matrix is totally dual integral. We investigate relationships between matrix classes in the LCP literature such as principally unimodular matrices. Principally unimodular matrices are known that all basic solutions to the LCP are integral for any integral input vector. In addition, we show that it is coNP-hard to decide whether a given LCP instance is totally dual integral.