Yusuke Kobayashi

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura et al.

We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

Chien-Chung Huang, Naonori Kakimura, Yusuke Kobayashi et al.

This paper studies randomized polynomial kernelization for the weighted $d$-matroid intersection problem. While the problem is known to have a kernel of size $O(d^{(k - 1)d})$ where $k$ is the solution size, the existence of a polynomial kernel is not known, except for the cases when either all the given matroids are partition matroids~(i.e., the $d$-dimensional matching problem) or all the given matroids are linearly representable. The main contribution of this paper is to develop a new kernelization technique for handling general matroids. We first show that the weighted $d$-matroid intersection problem admits a polynomial kernel when one matroid is arbitrary and the other $d-1$ matroids are partition matroids. Interestingly, the obtained kernel has size $\tilde{O}(k^d)$, which matches the optimal bound~(up to logarithmic factors) for the $d$-dimensional matching problem. This approach can be adapted to the case when $d-1$ matroids in the input belong to a more general class of matroids, including graphic, cographic, and transversal matroids. We also show that the problem has a kernel of pseudo-polynomial size when given $d-1$ matroids are laminar. Our technique finds a kernel such that any feasible solution of a given instance can reach a better solution in the kernel, which is sufficiently versatile to allow us to design parameterized streaming algorithms and faster EPTASs.

Yusuke Kobayashi, Takashi Noguchi

In the 2-Vertex-Connected Spanning Subgraph problem (2-VCSS), we are given an undirected graph $G$, and the objective is to find a 2-vertex-connected spanning subgraph $S$ of $G$ with the minimum number of edges. In the context of survivable network design, 2-VCSS is one of the most fundamental and well-studied problems. There has been active research on improving the approximation ratio of algorithms, and the current best ratio is $\frac{4}{3}$, achieved by Bosch-Calvo, Grandoni, and Jabal Ameli. In this paper, we improve the approximation ratio to $\frac{95}{72}+\varepsilon$ ($<1.32$). The key idea in our algorithm is to introduce a 2-edge-cover without certain cycle components, and use it as an initial solution.

Miguel Bosch-Calvo, Fabrizio Grandoni, Yusuke Kobayashi et al.

In the Weighted Triangle-Free 2-Matching problem (WTF2M), we are given an undirected edge-weighted graph. Our goal is to compute a maximum-weight subgraph that is a 2-matching (i.e., no node has degree more than $2$) and triangle-free (i.e., it does not contain any cycle with $3$ edges). One of the main motivations for this and related problems is their practical and theoretical connection with the Traveling Salesperson Problem and with some $2$-connectivity network design problems. WTF2M is not known to be NP-hard and at the same time no polynomial-time algorithm to solve it is known in the general case (polynomial-time algorithms are known only for some special cases). The best-known (folklore) approximation algorithm for this problem simply computes a maximum-weight 2-matching, and then drops the cheapest edge of each triangle: this gives a $2/3$ approximation. In this paper we present a PTAS for WTF2M, i.e., a polynomial-time $(1-\varepsilon)$-approximation algorithm for any given constant $\varepsilon>0$. Our result is based on a simple local-search algorithm and a non-trivial analysis.

Akitoshi Kawamura, Yusuke Kobayashi

Suppose we want to patrol a fence (line segment) using k mobile agents with given speeds v_1, ..., v_k so that every point on the fence is visited by an agent at least once in every unit time period. Czyzowicz et al. conjectured that the maximum length of the fence that can be patrolled is (v_1 + ... + v_k)/2, which is achieved by the simple strategy where each agent i moves back and forth in a segment of length v_i/2. We disprove this conjecture by a counterexample involving k = 6 agents. We also show that the conjecture is true for k = 2, 3.