論文 - 垣村　尚徳

Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs.

Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi

SIAM J. Discrete Math. （SIAM Journal on Discrete Mathematics）  31 （ 2 ） 766 - 782 2017年

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0895-4801

　概要を見る

© 2017 Society for Industrial and Applied Mathematics. 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.

• Access to Document (DOI)

Parameterized Complexity of Sparse Linear Complementarity Problems

Sumita H., Kakimura N., Makino K.

Algorithmica （Algorithmica）  79 （ 1 ） 42 - 65 2017年

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  1868-8969

　概要を見る

© 2016, Springer Science+Business Media New York. 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 the combined parameter. We also show that if we drop any of the three parameters, then the LCP is NP-hard or W[1]-hard. In addition, we show the nonexistence of a polynomial kernel for the LCP unless coNP ⊆ NP/poly.

• Access to Document (DOI)

Coloring immersion-free graphs.

Naonori Kakimura, Ken-ichi Kawarabayashi

J. Comb. Theory, Ser. B （Journal of Combinatorial Theory. Series B）  121   284 - 307 2016年11月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0095-8956

　概要を見る

© 2016 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. 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 Kk-minor is (k−1)-colorable, where Kkis 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 Kk-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, and2. for any positive integer k (k≥6), it is NP-complete to decide whether or not a given graph G without a Kk-immersion is (k−3)-colorable.

• Access to Document (DOI)

The Linear Complementarity Problems with a Few Variables per Constraint.

Hanna Sumita, Naonori Kakimura, Kazuhisa Makino

Math. Oper. Res. （Mathematics of Operations Research）  40 （ 4 ） 1015 - 1026 2015年11月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0364-765X

　概要を見る

© 2015 INFORMS. 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.

• Access to Document (DOI)

Fixed-parameter tractability for subset feedback set problems with parity constraints.

Naonori Kakimura, Ken-ichi Kawarabayashi

Theor. Comput. Sci. （Theoretical Computer Science）  576 （ 1 ） 61 - 76 2015年04月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0304-3975

　概要を見る

© 2015 Elsevier B.V. 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.

• Access to Document (DOI)

Matching problems with delta-matroid constraints

Kakimura N., Takamatsu M.

SIAM J. Discrete Math. 28 （ 2 ） 942 - 961 2014年

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0895-4801

　概要を見る

Given an undirected graph G = (V, E) and a directed graph D = (V, A), the master/slave matching problem is to find a matching of maximum cardinality in G such that for each arc (u; v) ∈ A with u being matched, v is also matched. This problem is known to be NP-hard in general, but polynomially solvable in a special case where the maximum size of a connected component of D is at most two. This paper investigates the master/slave matching problem in terms of delta-matroids, which is a generalization of matroids. We first observe that the above polynomially solvable constraint can be interpreted as delta-matroids. We then introduce a new class of matching problem with delta-matroid constraints, which can be solved in polynomial time. In addition, we discuss our problem with additional constraints such as capacity constraints. © 2012, Australian Computer Society, Inc.

• Access to Document (DOI)

Half-integral packing of odd cycles through prescribed vertices.

Naonori Kakimura, Ken-ichi Kawarabayashi

Combinatorica （Combinatorica）  33 （ 5 ） 549 - 572 2013年10月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0209-9683

　概要を見る

The well-known theorem of Erdo{double acute}s-Pósa 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 Erdo{double acute}s-Pósa-type result holds. We further try to generalize this result to packing S-cycles of odd length. In contrast to packing S-cycles, the Erdo{double acute}s-Pósa-type result does not hold for packing odd S-cycles. We then relax packing odd S-cycles to half-integral packing, and show the Erdo{double acute}s-Pósa-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. © 2013 János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.

• Access to Document (DOI)

On the number of matrices to generate a matrix * -algebra over the real field

Aiura D., Kakimura N., Murota K.

Linear Algebra and Its Applications （Linear Algebra and Its Applications）  438 （ 3 ） 1252 - 1266 2013年02月

研究論文（学術雑誌）, 共著, 査読有り

　概要を見る

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

• Access to Document (DOI)

Robust independence systems

Kakimura N., Makino K.

SIAM J. Discrete Math. 27 （ 3 ） 1257 - 1273 2013年

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0302-9743

　概要を見る

An independence system 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 α > 0, a set is said to be α-robust if for any k, it includes an α-approximation of the maximum k-independent set, where a set Y in is called k-independent if the size |Y| is at most k. In this paper, we show that every independence system has a -robust independent set, where denotes the exchangeability of . 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. © 2011 Springer-Verlag.

• Access to Document (DOI)

Packing cycles through prescribed vertices under modularity constraints

Kakimura N., Kawarabayashi K.

Advances in Applied Mathematics （Advances in Applied Mathematics）  49 （ 2 ） 97 - 110 2012年08月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0196-8858

　概要を見る

The well-known theorem of Erdos-Pósa 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-Pósa properties: The Erdos-Pósa property for cycles of length divisible by a fixed integer p (Thomassen, 1988 [19]).The Erdos-Pósa 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. © 2012 Elsevier Inc.

• Access to Document (DOI)

Computing knapsack solutions with cardinality robustness

Kakimura N., Makino K., Seimi K.

Japan Journal of Industrial and Applied Mathematics 29 （ 3 ） 469 - 483 2012年

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0302-9743

　概要を見る

In this paper, we study the robustness over the cardinality variation for the knapsack problem. For the knapsack problem and a positive number α ≤ 1, we say that a feasible solution is α-robust if, for any positive integer k, it includes an α-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 ε > 0, the problem of deciding whether the knapsack problem admits a (ν + ε)-robust solution is weakly NP-hard, where ν denotes the rank quotient of the corresponding knapsack system. Since the knapsack problem always admits a ν-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. © 2011 Springer-Verlag.

• Access to Document (DOI)

Packing Directed Circuits through Prescribed Vertices Bounded Fractionally.

Naonori Kakimura, Ken-ichi Kawarabayashi

SIAM J. Discrete Math. （SIAM Journal on Discrete Mathematics）  26 （ 3 ） 1121 - 1133 2012年

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0895-4801

　概要を見る

A seminal result of Reed et al. [Combinatorica, 16 (1996), pp. 535-554] says that a directed graph has either κ vertex-disjoint directed circuits or a set of at most f(κ) 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 κ and a vertex subset S, whose size may not depend on κ, 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 κ) 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 κ in polynomial time if it has a 1/5-integral packing of size k for a given directed graph and an integer κ. © 2012 Society for Industrial and Applied Mathematics.

• Access to Document (DOI)

Packing cycles through prescribed vertices.

Naonori Kakimura, Ken-ichi Kawarabayashi, Dániel Marx

J. Comb. Theory, Ser. B （Journal of Combinatorial Theory. Series B）  101 （ 5 ） 378 - 381 2011年09月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0095-8956

　概要を見る

The well-known theorem of Erdo{double acute accent}s and Pósa 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 Erdo{double acute accent}s-Pósa'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)=40k2log2k such that G\X has no cycle that intersects S. © 2011 Elsevier Inc.

• Access to Document (DOI)

Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem.

Naonori Kakimura

J. Comb. Theory, Ser. B （Journal of Combinatorial Theory. Series B）  100 （ 6 ） 650 - 670 2010年11月

研究論文（学術雑誌）, 単著, 査読有り,  ISSN  0095-8956

　概要を見る

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 Pólya'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. © 2010 Elsevier Inc.

• Access to Document (DOI)

A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices

Naonori Kakimura

Linear Algebra and Its Applications （Linear Algebra and Its Applications）  433 （ 4 ） 819 - 823 2010年10月

研究論文（学術雑誌）, 単著, 査読有り

　概要を見る

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, Sá, 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. © 2010 Elsevier Inc. All rights reserved.

• Access to Document (DOI)

Solving linear programs from sign patterns.

Satoru Iwata, Naonori Kakimura

Mathematical Programming （Mathematical Programming）  114 （ 2 ） 393 - 418 2008年08月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0025-5610

　概要を見る

This paper is an attempt to provide a connection between qualitative matrix theory and linear programming. A linear program cx | 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γ) time, where m is the number of rows of A and γ is the number of all nonzero entries in A, b, and c. © 2007 Springer-Verlag.

• Access to Document (DOI)

Sign-solvable linear complementarity problems

Naonori Kakimura

Linear Algebra and Its Applications 429 （ 2-3 ） 606 - 616 2008年07月

研究論文（学術雑誌）, 単著, 査読有り,  ISSN  0302-9743

　概要を見る

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. © Springer-Verlag Berlin Heidelberg 2007.

• Access to Document (DOI)

Computing the inertia from sign patterns

Naonori Kakimura, Satoru Iwata

Mathematical Programming （Springer）  110 （ 1 ） 229 - 244 2007年06月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0302-9743

　概要を見る

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. © Springer-Verlag Berlin Heidelberg 2005.

• Access to Document (DOI)

On Reachable Assignments Under Dichotomous Preferences

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

PRIMA 2022: Principles and Practice of Multi-Agent Systems （Springer International Publishing）     650 - 658 2023年

研究論文（学術雑誌）, 査読有り,  ISSN  0302-9743

　概要を見る

We consider the problem of determining whether a target item assignment can
be reached from an initial item assignment by a sequence of pairwise exchanges
of items between agents. In particular, we consider the situation where each
agent has a dichotomous preference over the items, that is, each agent
evaluates each item as acceptable or unacceptable. Furthermore, we assume that
communication between agents is limited, and the relationship is represented by
an undirected graph. Then, a pair of agents can exchange their items only if
they are connected by an edge and the involved items are acceptable. We prove
that this problem is PSPACE-complete even when the communication graph is
complete (that is, every pair of agents can exchange their items), and this
problem can be solved in polynomial time if an input graph is a tree.


• Access to Document (DOI)

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams∗

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi 0001, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms(SODA)    1342 - 1355 2022年

研究論文（国際会議プロシーディングス）, 査読有り