Yusuke Kobayashi 0001

SODA Conference 2022 Conference Paper

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

We initiate the study of k -edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2 k -edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k -edge-connected. This yields an “edge-flip based” new proof of Nash-Williams' theorem: an undirected graph G has a k -edge-connected orientation if and only if G is 2 k -edge-connected. As another consequence of the theorem, we prove that the edge-flip graph of k -edge-connected orientations of an undirected graph G is connected if G is (2 k + 2)-edge-connected. This has been known to be true only when k = 1.

MFCS Conference 2019 Conference Paper

The Perfect Matching Reconfiguration Problem

• Marthe Bonamy
• Nicolas Bousquet 0001
• Marc Heinrich
• Takehiro Ito
• Yusuke Kobayashi 0001
• Arnaud Mary
• Moritz Mühlenthaler
• Kunihiro Wasa

We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as P_4-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.

STOC Conference 2017 Conference Paper

A weighted linear matroid parity algorithm

• Satoru Iwata 0001
• Yusuke Kobayashi 0001

The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Lovász (1980) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem.

STOC Conference 2014 Conference Paper

An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem

• Ken-ichi Kawarabayashi
• Yusuke Kobayashi 0001
• Stephan Kreutzer

The excluded grid theorem, originally proved by Robertson and Seymour in Graph Minors V, is one of the most central results in the study of graph minors. It has found numerous applications in algorithmic graph structure theory, for instance as the basis for bidimensionality theory on graph classes excluding a fixed minor. In 1997, Reed [25] and later Johnson, Robertson, Seymour and Thomas [17] conjectured an analogous theorem for directed graphs, i.e. the existence of a function f : N → N such that every digraph of directed tree-width at least f ( k ) contains a directed grid of order k . In this paper, we make significant progress toward this conjecture. Namely, we prove that every digraph of directed tree-width at least f ( k ) contains a "half-integral" directed grid of order k . This structural result allows us to contribute to the disjoint paths problem. We show that the following can be done in polynomial time: Suppose that we are given a digraph G and k terminal pairs ( s 1 , t 1 ), ( s 2 , t 2 ),..., ( s k , t k ), where k is a fixed constant. In polynomial time, either • we can find k paths P 1 ,..., P k such that P i is from s i to t i for i = 1,..., k and every vertex in G is in at most four of the paths, or • we can conclude that G does not contain disjoint paths P 1 ,..., P k such that P i is from s i to t i for i = 1,..., k . To the best of our knowledge, this is the first positive result for the general directed disjoint paths problem. Note that the directed disjoint paths problem is NP-hard even for k = 2. Therefore, polynomial-time algorithms for semiintegral disjoint paths is the best one can hope for.

SODA Conference 2014 Conference Paper

The Generalized Terminal Backup Problem

• Attila Bernáth
• Yusuke Kobayashi 0001

FOCS Conference 2013 Conference Paper

All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs

• Ken-ichi Kawarabayashi
• Yusuke Kobayashi 0001

We study the following all-or-nothing multicommodity flow problem in planar graphs. Input: A graph G with n vertices and k pairs of vertices (s 1, t 1 ), (s 2, t 2 ), .. ., (s k, t k ) in G. Find: A largest subset W of {1, .. .. , k such that for every i in W, we can send one unit of flow between s i and t i. This problem is different from the well-known maximum edge-disjoint paths problem in that we do not require integral flows for the pairs. This problem is APX-hard even for trees, and a 2-approximation algorithm is known for trees. For general graphs, Chekuri et al. (STOC'04) give a poly-logarithmic factor approximation algorithm and show that a natural LP-relaxation has a poly-logarithmic integrality gap. This result is in contrast with the integrality gap Ω(√n) for the maximum edge-disjoint paths problem. Our main result considerably strengthens this result when an input graph is planar. Namely, for the all-or-nothing multicommodity flow problem in planar graphs, we give an O(1)-approximation algorithm and show that the integrality gap is O(1). In particular, in polynomial time, we can find an index set W with |W| = Ω(OPT) and eight s i -t i paths for each i in W such that each edge is used at most eight times in these paths (with multiplicity), where OPT is the optimal value of the LP-relaxation of the all-or-nothing multicommodity flow problem. Our result can be compared to the recent result by S'eguin-Charbonneau and Shepherd (FOCS'11) who give an O(1)-approximation algorithm for the maximum edge-disjoint paths problem in planar graphs with congestion 2 (but not implied by this result).

SODA Conference 2012 Conference Paper

Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing

• Naonori Kakimura
• Ken-ichi Kawarabayashi
• Yusuke Kobayashi 0001

SODA Conference 2012 Conference Paper

List-coloring graphs without subdivisions and without immersions

• Ken-ichi Kawarabayashi
• Yusuke Kobayashi 0001

STOC Conference 2011 Conference Paper

Breaking o(n 1/2 )-approximation algorithms for the edge-disjoint paths problem with congestion two

• Ken-ichi Kawarabayashi
• Yusuke Kobayashi 0001

In the maximum edge-disjoint paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be routed by edge-disjoint paths. An r-approximation algorithm for this problem is a polynomial time algorithm that finds at least OPT / r edge-disjoint paths, where OPT is the maximum possible. Currently, an O(n 1/2 )-approximation algorithm is best known for this problem even if a congestion of two is allowed, i.e., each edge is allowed to be used in at most two of the paths.

SODA Conference 2010 Conference Paper

The Edge Disjoint Paths Problem in Eulerian Graphs and 4-edge-connected Graphs

• Ken-ichi Kawarabayashi
• Yusuke Kobayashi 0001

We consider the following well-known problem, which is called the edge-disjoint paths problem. Input: A graph G with n vertices and m edges, k pairs of vertices ( s 1, t 1 ), ( s 2, t 2 ), …, ( s k, t k ) in G. Output: Edge-disjoint paths P 1, P 2, …, P k in G such that P i joins s i and t i for i = 1, 2, …, k. Robertson and Seymour's graph minor project gives rise to an O ( m 3 ) algorithm for this problem for any fixed k, but their proof of the correctness needs the whole Graph Minor project, spanning 23 papers and at least 500 pages proof. We give a faster algorithm and a simpler proof of the correctness for the edge-disjoint paths problem for any fixed k. Our results can be summarized as follows: 1. If an input graph G is either 4-edge-connected or Eulerian, then our algorithm only needs to look for the following three simple reductions: (i) Excluding vertices of high degree. (ii) Excluding ≤ 3-edge-cuts. (iii) Excluding large clique minors. 2. When an input graph G is either 4-edge-connected or Eulerian, the number of terminals k is allowed to be non-trivially superconstant number, up to k = O ((log log log n ) ½–ε ) for any ε > 0. Thus our hidden constant in this case is dramatically smaller than Robertson-Seymour's. In addition, if an input graph G is either 4-edge-connected planar or Eulerian planar, k is allowed to be O ((log n ) ½–ε ) for any ε > 0. The same thing holds for bounded genus graphs. Moreover, if an input graph is either 4-edge-connected H -minor-free or Eulerian H -minor-free for fixed graph H, k is allowed to be O ((log log n ) ½–ε ) for any ε > 0. 3. We also give our own algorithm for the edge-disjoint paths problem in general graphs. We basically follow Robertson-Seymour's algorithm, but we cut half of the proof of the correctness for their algorithm. In addition, the time complexity of our algorithm is O ( n 2 ), which is faster than Robertson and Seymour's.

SODA Conference 2009 Conference Paper

Algorithms for finding an induced cycle in planar graphs and bounded genus graphs

• Yusuke Kobayashi 0001
• Ken-ichi Kawarabayashi

In this paper, we consider the problem of finding an induced cycle passing through k given vertices, which we call the induced cycle problem. The significance of finding induced cycles stems from the fact that precise characterization of perfect graphs would require structures of graphs without an odd induced cycle, and its complement. There has been huge progress in the recent years, especially, the Strong Perfect Graph Conjecture was solved in [6]. Concerning recognition of perfect graphs, there had been a long-standing open problem for detecting an odd hole and its complement, and finally this was solved in [4]. Unfortunately, the problem of finding an induced cycle passing through two given vertices is NP-complete in a general graph [2]. However, if the input graph is constrained to be planar and k is fixed, then the induced cycle problem can be solved in polynomial time [13, 14, 16]. In particular, an O( n 2 ) time algorithm is given for the case k = 2 by McDiarmid, Reed, Schrijver and Shepherd [18], where n is the number of vertices of the input graph. Our main results in this paper are to improve their result in the following sense. 1. The number of vertices k is allowed to be non-trivially super constant number, up to. More precisely, when, then the ICP in planar graphs can be solved in O( n 2+ ∊ ) time for any ∊ > 0. 2. The time complexity is linear if the given graph is planar and k is fixed. 3. The above results are extended to graphs embedded in a fixed surface. We note that the linear time algorithm (the second result) is independent from the first result. Let us point out that we give the first polynomial time algorithm for the problem for the bounded genus case. In fact, our proof gives a short proof of a result announced in [20] (without complete proof) which gives a linear time algorithm for the disjoint paths problem for fixed k for the bounded genus case. We also extend this result to the induced disjoint paths problem. Let us observe that if k is as a part of the input, then the problem is still NP-complete, and so we need to impose some condition on k.