8 Search Results for "Xiao, Mingyu"


Document
Connectivity in the Presence of an Opponent

Authors: Zihui Liang, Bakh Khoussainov, Toru Takisaka, and Mingyu Xiao

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
The paper introduces two player connectivity games played on finite bipartite graphs. Algorithms that solve these connectivity games can be used as subroutines for solving Müller games. Müller games constitute a well established class of games in model checking and verification. In connectivity games, the objective of one of the players is to visit every node of the game graph infinitely often. The first contribution of this paper is our proof that solving connectivity games can be reduced to the incremental strongly connected component maintenance (ISCCM) problem, an important problem in graph algorithms and data structures. The second contribution is that we non-trivially adapt two known algorithms for the ISCCM problem to provide two efficient algorithms that solve the connectivity games problem. Finally, based on the techniques developed, we recast Horn’s polynomial time algorithm that solves explicitly given Müller games and provide the first correctness proof of the algorithm. Our algorithms are more efficient than that of Horn’s algorithm. Our solution for connectivity games is used as a subroutine in the algorithm.

Cite as

Zihui Liang, Bakh Khoussainov, Toru Takisaka, and Mingyu Xiao. Connectivity in the Presence of an Opponent. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 79:1-79:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{liang_et_al:LIPIcs.ESA.2023.79,
  author =	{Liang, Zihui and Khoussainov, Bakh and Takisaka, Toru and Xiao, Mingyu},
  title =	{{Connectivity in the Presence of an Opponent}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{79:1--79:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.79},
  URN =		{urn:nbn:de:0030-drops-187324},
  doi =		{10.4230/LIPIcs.ESA.2023.79},
  annote =	{Keywords: Explicit M\"{u}ller games, games played on finite graphs, winning strategies, synthesis and analysis of games}
}
Document
Improved Approximation Algorithms for the Traveling Tournament Problem

Authors: Jingyang Zhao, Mingyu Xiao, and Chao Xu

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other’s home venue, minimizing the total distance traveled by all n teams (n is even). TTP-k is the problem with one more constraint that each team can have at most k consecutive home games or away games. The case where k = 3, TTP-3, is one of the most investigated cases. In this paper, we improve the approximation ratio of TTP-3 from (1.667+ε) to (1.598+ε), for any ε > 0. Previous schedules were constructed based on a Hamiltonian cycle of the graph. We propose a novel construction based on triangle packing. Then, by combining our triangle packing schedule with the Hamiltonian cycle schedule, we obtain the improved approximation ratio. The idea of our construction can also be extended to k ≥ 4. We demonstrate that the approximation ratio of TTP-4 can be improved from (1.750+ε) to (1.700+ε) by the same method. As an additional product, we also improve the approximation ratio of LDTTP-3 (TTP-3 where all teams are allocated on a straight line) from 4/3 to (6/5+ε).

Cite as

Jingyang Zhao, Mingyu Xiao, and Chao Xu. Improved Approximation Algorithms for the Traveling Tournament Problem. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 83:1-83:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{zhao_et_al:LIPIcs.MFCS.2022.83,
  author =	{Zhao, Jingyang and Xiao, Mingyu and Xu, Chao},
  title =	{{Improved Approximation Algorithms for the Traveling Tournament Problem}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{83:1--83:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.83},
  URN =		{urn:nbn:de:0030-drops-168813},
  doi =		{10.4230/LIPIcs.MFCS.2022.83},
  annote =	{Keywords: Sports scheduling, Traveling Tournament Problem, Approximation algorithm}
}
Document
Faster FPT Algorithm for 5-Path Vertex Cover

Authors: Radovan Červený and Ondřej Suchý

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
The problem of d-Path Vertex Cover, d-PVC lies in determining a subset F of vertices of a given graph G=(V,E) such that G \ F does not contain a path on d vertices. The paths we aim to cover need not to be induced. It is known that the d-PVC problem is NP-complete for any d >= 2. When parameterized by the size of the solution k, 5-PVC has direct trivial algorithm with O(5^kn^{O(1)}) running time and, since d-PVC is a special case of d-Hitting Set, an algorithm running in O(4.0755^kn^{O(1)}) time is known. In this paper we present an iterative compression algorithm that solves the 5-PVC problem in O(4^kn^{O(1)}) time.

Cite as

Radovan Červený and Ondřej Suchý. Faster FPT Algorithm for 5-Path Vertex Cover. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{cerveny_et_al:LIPIcs.MFCS.2019.32,
  author =	{\v{C}erven\'{y}, Radovan and Such\'{y}, Ond\v{r}ej},
  title =	{{Faster FPT Algorithm for 5-Path Vertex Cover}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.32},
  URN =		{urn:nbn:de:0030-drops-109761},
  doi =		{10.4230/LIPIcs.MFCS.2019.32},
  annote =	{Keywords: graph algorithms, Hitting Set, iterative compression, parameterized complexity, d-Path Vertex Cover}
}
Document
Brief Announcement
Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable

Authors: Mingyu Xiao and Hiroshi Nagamochi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
In the bounded-degree cut problem, we are given a multigraph G=(V,E), two disjoint vertex subsets A,B subseteq V, two functions u_A, u_B:V -> {0,1,...,|E|} on V, and an integer k >= 0. The task is to determine whether there is a minimal (A,B)-cut (V_A,V_B) of size at most k such that the degree of each vertex v in V_A in the induced subgraph G[V_A] is at most u_A(v) and the degree of each vertex v in V_B in the induced subgraph G[V_B] is at most u_B(v). In this paper, we show that the bounded-degree cut problem is fixed-parameter tractable by giving a 2^{18k}|G|^{O(1)}-time algorithm. This is the first single exponential FPT algorithm for this problem. The core of the algorithm lies two new lemmas based on important cuts, which give some upper bounds on the number of candidates for vertex subsets in one part of a minimal cut satisfying some properties. These lemmas can be used to design fixed-parameter tractable algorithms for more related problems.

Cite as

Mingyu Xiao and Hiroshi Nagamochi. Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 112:1-112:6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{xiao_et_al:LIPIcs.ICALP.2018.112,
  author =	{Xiao, Mingyu and Nagamochi, Hiroshi},
  title =	{{Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{112:1--112:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.112},
  URN =		{urn:nbn:de:0030-drops-91164},
  doi =		{10.4230/LIPIcs.ICALP.2018.112},
  annote =	{Keywords: FPT, Important Cuts, Graph Cuts, Graph Algorithms}
}
Document
A Linear-Time Algorithm for Integral Multiterminal Flows in Trees

Authors: Mingyu Xiao and Hiroshi Nagamochi

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)


Abstract
In this paper, we study the problem of finding an integral multiflow which maximizes the sum of flow values between every two terminals in an undirected tree with a nonnegative integer edge capacity and a set of terminals. In general, it is known that the flow value of an integral multiflow is bounded by the cut value of a cut-system which consists of disjoint subsets each of which contains exactly one terminal or has an odd cut value, and there exists a pair of an integral multiflow and a cut-system whose flow value and cut value are equal; i.e., a pair of a maximum integral multiflow and a minimum cut. In this paper, we propose an O(n)-time algorithm that finds such a pair of an integral multiflow and a cut-system in a given tree instance with n vertices. This improves the best previous results by a factor of Omega(n). Regarding a given tree in an instance as a rooted tree, we define O(n) rooted tree instances taking each vertex as a root, and establish a recursive formula on maximum integral multiflow values of these instances to design a dynamic programming that computes the maximum integral multiflow values of all O(n) rooted instances in linear time. We can prove that the algorithm implicitly maintains a cut-system so that not only a maximum integral multiflow but also a minimum cut-system can be constructed in linear time for any rooted instance whenever it is necessary. The resulting algorithm is rather compact and succinct.

Cite as

Mingyu Xiao and Hiroshi Nagamochi. A Linear-Time Algorithm for Integral Multiterminal Flows in Trees. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 62:1-62:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{xiao_et_al:LIPIcs.ISAAC.2016.62,
  author =	{Xiao, Mingyu and Nagamochi, Hiroshi},
  title =	{{A Linear-Time Algorithm  for Integral Multiterminal Flows in Trees}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{62:1--62:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.62},
  URN =		{urn:nbn:de:0030-drops-68311},
  doi =		{10.4230/LIPIcs.ISAAC.2016.62},
  annote =	{Keywords: Multiterminal flow; Maximum flow; Minimum Cut; Trees; Linear-time algorithms}
}
Document
An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two

Authors: Mingyu Xiao and Shaowei Kou

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
The Traveling Tournament Problem is a complex combinatorial optimization problem in tournament timetabling, which asks a schedule of home/away games meeting specific feasibility requirements, while also minimizing the total distance traveled by all the n teams (n is even). Despite intensive algorithmic research on this problem over the last decade, most instances with more than 10 teams in well-known benchmarks are still unsolved. In this paper, we give a practical approximation algorithm for the problem with constraints such that at most two consecutive home games or away games are allowed. Our algorithm, that generates feasible schedules based on minimum perfect matchings in the underlying graph, not only improves the previous approximation ratio from (1+16/n) to about (1+4/n) but also has very good experimental performances. By applying our schedules on known benchmark sets, we can beat all previously-known results of instances with n being a multiple of 4 by 3% to 10%.

Cite as

Mingyu Xiao and Shaowei Kou. An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 89:1-89:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{xiao_et_al:LIPIcs.MFCS.2016.89,
  author =	{Xiao, Mingyu and Kou, Shaowei},
  title =	{{An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{89:1--89:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.89},
  URN =		{urn:nbn:de:0030-drops-64976},
  doi =		{10.4230/LIPIcs.MFCS.2016.89},
  annote =	{Keywords: sports scheduling, traveling tournament problem, approximation algorithms, timetabling combinatorial optimization}
}
Document
Parameterized Complexity of Critical Node Cuts

Authors: Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, and Barak Navon

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)


Abstract
We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of parameterized complexity. That is, we are interested in whether or not this problem is solvable in f(kappa) * n^{O(1)} time (i.e., whether or not it is fixed-parameter tractable), for various natural parameters kappa. We consider four such parameters: - The size k of the required cut. - The upper bound x on the number of remaining connected pairs. - The lower bound y on the number of connected pairs to be removed. - The treewidth w of G. We determine whether or not CNC is fixed-parameter tractable for each of these parameters. We determine this also for all possible aggregations of these four parameters, apart from w+k. Moreover, we also determine whether or not CNC admits a polynomial kernel for all these parameterizations. That is, whether or not there is an algorithm that reduces each instance of CNC in polynomial time to an equivalent instance of size kappa^{O(1)}, where kappa is the given parameter.

Cite as

Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, and Barak Navon. Parameterized Complexity of Critical Node Cuts. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 343-354, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{hermelin_et_al:LIPIcs.IPEC.2015.343,
  author =	{Hermelin, Danny and Kaspi, Moshe and Komusiewicz, Christian and Navon, Barak},
  title =	{{Parameterized Complexity of Critical Node Cuts}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{343--354},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.343},
  URN =		{urn:nbn:de:0030-drops-55950},
  doi =		{10.4230/LIPIcs.IPEC.2015.343},
  annote =	{Keywords: graph cut problem, NP-hard problem, treewidth}
}
Document
Parameterized Complexity Dichotomy for Steiner Multicut

Authors: Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = \{T_{1},...,T_{t}}, T_i \subseteq V(G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set T_{i} at least one pair of terminals is in different connected components of G \ S. This problem generalizes several well-studied graph cut problems, in particular the Multicut problem, which corresponds to the case p = 2. The Multicut problem was recently shown to be fixed-parameter tractable for parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. The question whether this result generalizes to Steiner Multicut motivates the present work. We answer the question that motivated this work, and in fact provide a dichotomy of the parameterized complexity of Steiner Multicut on general graphs. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). Among the many results in the paper, we highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for parameter k+t on general graphs (but has no polynomial kernel, even on trees). - In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs. - All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1) as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).

Cite as

Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized Complexity Dichotomy for Steiner Multicut. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 157-170, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.STACS.2015.157,
  author =	{Bringmann, Karl and Hermelin, Danny and Mnich, Matthias and van Leeuwen, Erik Jan},
  title =	{{Parameterized Complexity Dichotomy for Steiner Multicut}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{157--170},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.157},
  URN =		{urn:nbn:de:0030-drops-49115},
  doi =		{10.4230/LIPIcs.STACS.2015.157},
  annote =	{Keywords: graph cut problems, Steiner cut, fixed-parameter tractability}
}
  • Refine by Author
  • 5 Xiao, Mingyu
  • 2 Hermelin, Danny
  • 2 Nagamochi, Hiroshi
  • 1 Bringmann, Karl
  • 1 Kaspi, Moshe
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Fixed parameter tractability
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Dynamic graph algorithms
  • Show More...

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Explicit Müller games
  • 1 FPT
  • 1 Graph Algorithms
  • 1 Graph Cuts
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2015
  • 2 2016
  • 1 2018
  • 1 2019
  • 1 2022
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail