Mingyu Xiao

TCS Journal 2026 Journal Article

A Fast Algorithm for Maximum Satisfiability above Half Number of Clauses

• Junqiang Peng
• Mingyu Xiao

We study the following parameterization of the MaxSAT problem: Given a CNF formula with m clauses, decide whether at least m/2 + μ clauses in the formula could be satisfied, where μ is the excess of the number of satisfied clauses over the trivial lower bound m/2 and is taken as the parameter. This perspective is known as the above guarantee parameterization. Since its introduction by Mahajan and Raman in 1999, the analysis of parameterization above guarantee has become a highly active and fruitful line of research. In this paper, we develop a new algorithm with runtime O*(2.1479^μ), significantly improving the previous best upper bound O*(5.4064^μ).

AAAI Conference 2026 Conference Paper

A TSP-Based Algorithm for Multi-League Traveling Tournament

• Jingyang Zhao
• Mingyu Xiao
• Ken-ichi Kawarabayashi

In some professional sports leagues, inter-league games are scheduled among multiple divisions or conferences. This inspired us to study the p-partite Traveling Tournament Problem (p-partite TTP), where teams are partitioned into p leagues, and each team plays games against teams from different leagues. Previously, only the case of p=2, known as the Bipartite TTP or BTTP, has been introduced and studied. In this paper, we show that the p-partite TTP is NP-hard for any fixed p≥3, and we propose an efficient algorithm based on a solution to the Traveling Salesman Problem. Furthermore, we prove that the algorithm achieves a notable approximation ratio of 8/3+O(1/n) when p=3. We also conduct experiments demonstrating that the algorithm produces practical schedules with significantly reduced total travel distances, highlighting its effectiveness in generating high-quality multipartite tournament schedules.

I&C Journal 2026 Journal Article

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem

• Jingyang Zhao
• Mingyu Xiao
• Shunwang Wang

The Capacitated Location Routing Problem is an important planning and routing problem in logistics, which generalizes the capacitated vehicle routing problem and the uncapacitated facility location problem. In this problem, we are given a set of depots and a set of customers where each depot has an opening cost and each customer has a demand. The goal is to open some depots and route capacitated vehicles from the opened depots to satisfy all customers’ demand, while minimizing the total cost. In this paper, we propose a 4. 169-approximation algorithm for this problem, improving the best-known 4. 38-approximation ratio. If the demand of each customer is allowed to be delivered by multiple tours, we propose a more refined 4. 091-approximation algorithm. Experimental study on benchmark instances shows that the quality of our computed solutions is better than that of the previous algorithm and is also much closer to optimality than the provable approximation factor. Moreover, our approaches can be extended to obtain improved approximation algorithms for several known variants, including splittable prize-collecting, splittable grouping, and both splittable and unsplittable cross-docking.

I&C Journal 2026 Journal Article

Exponential time algorithms for deciding regular games

• Zihui Liang
• Bakh Khoussainov
• Mingyu Xiao

Regular games constitute a fundamental class used in the analysis and synthesis of reactive systems. This class includes colored Muller games, McNaughton games, Muller games, Rabin games, and Streett games. These games are played on directed graphs G, where Player 0 and Player 1 construct an infinite path ρ through G. The outcome is determined by the set X of vertices visited infinitely often along ρ. Regular games are determined, meaning the graph G can be partitioned into two sets, W i n 0 ( G ) and W i n 1 ( G ), representing the winning positions for Player 0 and Player 1, respectively. Various algorithms exist for specific types of regular games that compute these sets. In this paper, we seek general principles for designing algorithms that solve all regular games. Our approach relies on recursive and dynamic programming techniques that make use of standard concepts such as subgames and traps. We demonstrate that our methods match or improve upon the performance of existing algorithms for all regular games mentioned above.

AAAI Conference 2026 Conference Paper

FPT Approximation Algorithms for TSP on Non-Metric Graphs

• Jingyang Zhao
• Zimo Sheng
• Mingyu Xiao

TSP is a classic and extensively studied problem with numerous real-world applications in artificial intelligence and operations research. It is well-known that TSP admits a constant approximation ratio on metric graphs but becomes NP-hard to approximate within any computable function f(n) on general graphs. This disparity highlights a significant gap between the results on metric graphs and general graphs. Recent research has introduced some parameters to measure the ``distance'' of general graphs from being metric and explored FPT approximation algorithms parameterized by these parameters. Two commonly studied parameters are p, the number of vertices in triangles violating the triangle inequality, and q, the minimum number of vertices whose removal results in a metric graph. In this paper, we present improved FPT approximation algorithms with respect to these two parameters. For p, we propose an FPT algorithm with a 1.5-approximation ratio, improving upon the previous ratio of 2.5. For q, we significantly enhance the approximation ratio from 11 to 3, advancing the state of the art in both cases.

AAAI Conference 2026 Conference Paper

How Hard Is It to Rig a Tournament When Few Players Can Beat or Be Beaten by the Favorite?

• Zhonghao Wang
• Junqiang Peng
• Yuxi Liu
• Mingyu Xiao

In knockout tournaments, players compete in successive rounds, with losers eliminated and winners advancing until a single champion remains. Given a tournament digraph D, which encodes the outcomes of all possible matches, and a designated player v* in V(D), the Tournament Fixing problem (TFP) asks whether the tournament can be scheduled in a way that guarantees v* emerges as the winner. TFP is known to be NP-hard, but is fixed-parameter tractable (FPT) when parameterized by structural measures such as the feedback arc set (fas) or feedback vertex set (fvs) number of the tournament digraph. In this paper, we introduce and study two new structural parameters: the number of players who can defeat v* (i.e., the in-degree of v*, denoted by k) and the number of players that v* can defeat (i.e., the out-degree of v*, denoted by l). A natural question is that: can TFP be efficiently solved when k or l is small? We answer this question affirmatively by showing that TFP is FPT when parameterized by either the in-degree or out-degree of v*. Our algorithm for the in-degree parameterization is particularly involved and technically intricate. Notably, the in-degree k can remain small even when other structural parameters, such as fas or fvs, are large. Hence, our results offer a new perspective and significantly broaden the parameterized algorithmic understanding of the Tournament Fixing problem.

AAAI Conference 2026 Conference Paper

Improved Algorithms for Trip-Vehicle Assignment in Ride-Sharing

• Jingyang Zhao
• Mingyu Xiao
• Yonghang Su

The Ride-Sharing Assignment Problem (AAAI 2018) is a fundamental problem in intelligent transportation systems, urban mobility, and algorithmic decision-making. Given a set of m vehicles with initial locations and n requests (n≤mk), each with a specified origin and destination, the goal is to assign at most k requests to each vehicle and compute corresponding routes that minimize the total travel distance. The algorithmic approach depends on whether n=mk or n

I&C Journal 2026 Journal Article

Improved approximations for the capacitated vehicle routing problem with fixed capacity

• Jingyang Zhao
• Mingyu Xiao

The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Based on customer demand, we distinguish three variants of CVRP: unit-demand, splittable, and unsplittable. In this paper, we consider k-CVRP in general metrics and on general graphs, where k is the vehicle capacity. All three versions are APX-hard for any fixed k ≥ 3. Based on an α-approximation algorithm for metric TSP, we propose new approximation algorithms. For α = 3 2, we obtain a ( 5 2 − Θ ( 1 k ) ) -approximation algorithm for the splittable and unit-demand cases, and a ( 5 2 + ln ⁡ 2 − Θ ( 1 k ) ) -approximation algorithm for the unsplittable case. Our approximation ratio is better than the previous results when k is less than a fairly large value, approximately 1. 7 × 10 7. For small values of k, we design independent and elegant algorithms with further improvements. For the splittable and unit-demand cases, we improve the approximation ratio from 1. 792 to 1. 500 for k = 3, and from 1. 750 to 1. 500 for k = 4. For the unsplittable case, we improve the approximation ratio from 1. 792 to 1. 500 for k = 3, from 2. 051 to 1. 750 for k = 4, and from 2. 249 to 2. 157 for k = 5. The approximation ratio for k = 3 surprisingly achieves the same value as in the splittable case. Our techniques, such as EX-ITP – an extension of the classic ITP method, have the potential to improve algorithms for other routing problems as well.

I&C Journal 2026 Journal Article

Solving Co-Path/Cycle Packing and Co-Path Packing faster than 3k

• Yuxi Liu
• Mingyu Xiao

The Co-Path/Cycle Packing problem (resp. The Co-Path Packing problem) asks whether we can delete at most k vertices from the input graph such that the remaining graph is a collection of induced paths and cycles (resp. induced paths). These two problems are fundamental graph problems that have important applications in bioinformatics. Although these two problems have been extensively studied in parameterized algorithms, it seems hard to break the running time bound 3 k. In 2015, Feng et al. provided an O ⁎ ( 3 k ) -time randomized algorithm for both of them. Recently, Tsur showed that they can be solved in O ⁎ ( 3 k ) time deterministically. In this paper, by combining several techniques such as path decomposition, dynamic programming, cut & count, and branch-and-search methods, we show that Co-Path/Cycle Packing can be solved in O ⁎ ( 2. 8192 k ) time deterministically and Co-Path Packing can be solved in O ⁎ ( 2. 9241 k ) time with failure probability ≤ 1 / 3. As a by-product, we also show that the Co-Path Packing problem can be solved in O ⁎ ( 5 p ) time with probability at least 2/3 if a path decomposition of width p is given.

I&C Journal 2026 Journal Article

Solving Subset Feedback Vertex Set in Chordal Graphs Faster than 2k

• Tian Bai
• Mingyu Xiao

The Subset Feedback Vertex Set problem (SFVS) is to delete k vertices from a given graph such that in the remaining graph, any vertex in a subset T of vertices (called a terminal set) is not in a cycle. The famous Feedback Vertex Set problem is the special case of SFVS with T being the whole set of vertices. In this paper, we study exact algorithms for SFVS in Split Graphs (SFVS-S) and SFVS in Chordal Graphs (SFVS-C). SFVS-S generalizes the minimum vertex cover problem and the prize-collecting version of the maximum independent set problem on hypergraphs (PCMIS), and SFVS-C further generalizes SFVS-S. Both SFVS-S and SFVS-C are implicit 3-Hitting Set problems. However, it is not easy to solve them faster than 3-Hitting Set. In 2019, Philip, Rajan, Saurabh, and Tale proved that SFVS-C can be solved in O * ( 2 k ) time, slightly improving the best result O * ( 2. 0755 k ) for 3-Hitting Set. In this paper, we break the “2 k -barrier” for SFVS-S and SFVS-C by introducing an O * ( 1. 8192 k ) -time algorithm. This achievement also indicates that PCMIS can be solved in O * ( 1. 8192 n ) time, marking the first exact algorithm for PCMIS that outperforms the trivial O * ( 2 n ) threshold. Our algorithm uses reduction and branching rules based on the Dulmage-Mendelsohn decomposition and a divide-and-conquer method.

AAAI Conference 2025 Conference Paper

A Matching-Based Algorithm for the Traveling Tournament Problem

• Jingyang Zhao
• Mingyu Xiao

The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling. It involves designing a feasible double round-robin tournament for a sports league of n teams under several feasibility requirements, while minimizing the total traveling costs of the teams. The parameter k requires that in the tournament at most k consecutive home games or away games for each team are allowed. TTP-k with a small k, especially for k=2,3 and 4, have been extensively studied in the literature. In this paper, we focus on TTP-4 and design an efficient algorithm for it based on minimum weight matching. In theory, we prove that our algorithm has an approximation ratio of 1.625+ε for any constant ε>0, improving the best-known approximation ratio of 1.7+ε. In practice, our experimental results indicate an average improvement of 6.65% over the best-known solutions on 9 benchmark instances.

TCS Journal 2025 Journal Article

A matching-based approximation algorithm for the traveling tournament problem

• Jingyang Zhao
• Mingyu Xiao

The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling. It involves designing a feasible double round-robin tournament for a sports league of n teams under several feasibility requirements, while minimizing the total traveling costs of the teams. The parameter k requires that in the tournament at most k consecutive home games or away games for each team are allowed. TTP-k with a small k, especially for k = 2, 3 and 4, have been extensively studied in the literature. In this paper, we focus on TTP-4 and design an efficient algorithm for it based on minimum weight matching. In theory, we prove that our algorithm has an approximation ratio of 1. 625 + ε for any constant ε > 0, improving the best-known approximation ratio of 1. 7 + ε. In practice, our experimental results indicate an average improvement of 6. 65% over the best-known solutions on 9 benchmark instances.

TCS Journal 2025 Journal Article

An improved kernel and parameterized algorithm for deletion to induced matching

• Yuxi Liu
• Mingyu Xiao

A graph is called an induced matching if each vertex in the graph is a degree-1 vertex. The Deletion to Induced Matching problem asks whether we can delete at most k vertices from the input graph such that the remaining graph is an induced matching. This paper studies parameterized algorithms for this problem by taking the size k of the deletion set as the parameter. First, we prove a 6k-vertex kernel for this problem, improving the previous result of 7k. Second, we give an O ⁎ ( 1. 6477 k ) -time and polynomial-space algorithm, improving the previous running-time bound of O ⁎ ( 1. 7485 k ).

TCS Journal 2025 Journal Article

Approximation algorithms for cycle and path partitions in complete graphs

• Jingyang Zhao
• Mingyu Xiao

Given an edge-weighted (metric/general) complete graph with n vertices, where n mod k = 0, the maximum weight (metric/general) k-cycle/path partition problem is to find a set of n k vertex-disjoint k-cycles/paths such that the total weight is maximized. In this paper, we consider approximation algorithms. For metric k-cycle partition, we improve the previous approximation ratio from 3 5 to 7 10 for k = 5, and from 7 8 ( 1 − 1 k ) 2 for k > 5 to ( 7 8 − 1 8 k ) ( 1 − 1 k ) for constant odd k > 5 and to 7 8 ( 1 − 1 k + 1 k ( k − 1 ) ) for even k > 5. For metric k-path partition, we improve the approximation ratio from 7 8 ( 1 − 1 k ) to 27 k 2 − 48 k + 16 32 k 2 − 36 k − 24 for k ∈ { 6, 8, 10 }. For the case of k = 4, we improve the approximation ratio from 3 4 to 5 6 for metric 4-cycle partition, from 2 3 to 3 4 for general 4-cycle partition, and from 3 4 to 14 17 for metric 4-path partition.

TCS Journal 2025 Journal Article

Fast exact algorithms for the SAT problem with bounded occurrences of variables

• Junqiang Peng
• Mingyu Xiao

We present fast algorithms for the general CNF satisfiability problem (SAT) with running-time bound O ⁎ ( c d n ), where c d is a function of the maximum occurrence d of variables (d can also be the average occurrence when each variable appears at least twice), and n is the number of variables in the input formula. Similar to SAT with bounded clause lengths, SAT with bounded occurrences of variables has also been extensively studied in the literature. Especially, the running-time bounds for small values of d, such as d = 3 and d = 4, have become bottlenecks for algorithms evaluated by the formula length L and other algorithms. In this paper, we show that SAT can be solved in time O ⁎ ( 1. 1238 n ) for d = 3 and O ⁎ ( 1. 2628 n ) for d = 4, improving the previous results O ⁎ ( 1. 1279 n ) and O ⁎ ( 1. 2721 n ) obtained by Wahlström (SAT 2005) nearly 20 years ago. For d ≥ 5, we obtain a running time bound of O ⁎ ( 1. 0641 d n ), implying a bound of O ⁎ ( 1. 0641 L ) with respect to the formula length L.

AAAI Conference 2025 Conference Paper

Improved Approximation Algorithms for Clustered TSP and Subgroup Planning

• Jingyang Zhao
• Mingyu Xiao
• Junqiang Peng
• Ziliang Xiong

In the Clustered TSP (CTSP), we are given an edge-weighted graph satisfying the triangle inequality property, and a family of pairwise disjoint vertex groups. The goal is to find a minimum weight tour that includes all vertices, ensuring that the vertices within each group appear consecutively on the tour. The subgroup planning problem (SGPP) is an extension of CTSP by relaxing some triangle inequality requirements on edge weights. CTSP and SGPP have plentiful applications in AI and robotics. In this paper, we design three improved approximation algorithms for SGPP and CTSP. First, we propose a polynomial-time 2.167-approximation algorithm for SGPP, improving the previous ratio of 3 (IJCAI 2017). Second, we give an FPT 2.072-approximation algorithm for SGPP parameterized by the maximum group size, improving the previous ratio of 2.5 (IJCAI 2017). Third, we prove an FPT (β<1.5)-approximation algorithm for SGPP parameterized by the number of groups, which even improves the previous ratio 1.667 for CTSP (ORL 1999). We also conduct experiments to evaluate the performance of our algorithms.

TCS Journal 2025 Journal Article

Multidepot capacitated vehicle routing with improved approximation guarantees

• Jingyang Zhao
• Mingyu Xiao

The Multidepot Capacitated Vehicle Routing Problem (k-MCVRP) is a well-known variant of the classic Capacitated Vehicle Routing Problem (k-CVRP), where a set of vehicles, each with a capacity of k, are stationed at multiple depots. The goal is to route the vehicles to serve customers' demand while ensuring that each vehicle returns to its starting depot and the total traveling distance is minimized. There are three variants of k-MCVRP according to the property of the demand: unit-demand, splittable and unsplittable. In this paper, we study approximation algorithms for k-MCVRP in metric graphs. The best-known approximation ratios for these three versions are 2 α + 1 − Θ ( 1 / k ), 2 α + 1 − Θ ( 1 / k ), and 4, respectively, where α denotes the approximation ratio of metric TSP. Assuming α = 3 / 2, we propose a ( 4 − 1 / 1500 ) -approximation algorithm for the splittable and unit-demand cases, and a ( 4 − 1 / 50000 ) -approximation algorithm for the unsplittable case. When k is a fixed integer, we further give a ( 3 + ln ⁡ 2 − max ⁡ { Θ ( 1 / k ), 1 / 9000 } ) -approximation algorithm for the splittable and unit-demand cases, and a ( 3 + ln ⁡ 2 − Θ ( 1 / k ) ) -approximation algorithm for the unsplittable case. Our results are based on recent progress in approximating k-CVRP.

TCS Journal 2025 Journal Article

Network control games played on graphs

• Zihui Liang
• Bakh Khoussainov
• Mingyu Xiao

We study network-control games played on graphs. These games belong to the class of scoring games in combinatorial game theory. In a network-control game, two players alternate in rounds on a given graph. During each round, a player selects an unclaimed vertex with its unclaimed neighbours within the distance t. The objective is to decide which player can claim more vertices at the end of the play. We study network-control games on various classes of graphs, including paths, linear forests, and hub-and-spoke graphs. Additionally, we examine greedy, symmetric, and optimal strategies. In the context of scoring games, concepts and techniques developed in this paper contribute to the further understanding and development of combinatorial game theory.

IJCAI Conference 2025 Conference Paper

New Algorithms for #2-SAT and #3-SAT

• Junqiang Peng
• Zimo Sheng
• Mingyu Xiao

The #2-SAT and #3-SAT problems involve counting the number of satisfying assignments (also called models) for instances of 2-SAT and 3-SAT, respectively. In 2010, Zhou et al. (https: //doi. org/10. 1609/aaai. v24i1. 7537) proposed an O*(1. 1892^m)-time algorithm for #2-SAT and an efficient approach for #3-SAT, where m denotes the number of clauses. In this paper, we show that the weighted versions of #2-SAT and #3-SAT can be solved in O*(1. 1082^m) and O*(1. 4423^m) time, respectively. These results directly apply to the unweighted cases and achieve substantial improvements over the previous results. These advancements are enabled by the introduction of novel reduction rules, a refined analysis of branching operations, and the application of path decompositions on the primal and dual graphs of the formula.

IJCAI Conference 2025 Conference Paper

Strategyproofness and Monotone Allocation of Auction in Social Networks

• Yuhang Guo
• Dong Hao
• Bin Li
• Mingyu Xiao
• Bakh Khoussainov

Strategyproofness in network auctions requires that bidders not only report their valuations truthfully, but also do their best to invite neighbours from the social network. In contrast to canonical auctions, where the value-monotone allocation in Myerson's Lemma is a cornerstone, a general principle of allocation rules for strategyproof network auctions is still missing. We show that, due to the absence of such a principle, even extensions to multi-unit network auctions with single-unit demand present unexpected difficulties, and all pioneering researches fail to be strategyproof. For the first time in this field, we identify two categories of monotone allocation rules on networks: Invitation-Depressed Monotonicity (ID-MON) and Invitation-Promoted Monotonicity (IP-MON). They encompass all existing allocation rules of network auctions as specific instances. For any given ID-MON or IP-MON allocation rule, we characterize the existence and sufficient conditions for the strategyproof payment rules, and show that among all such payment rules, the revenue-maximizing one exists and is computationally feasible. With these results, the obstacle of combinatorial network auction with single-minded bidders is now resolved.

TCS Journal 2025 Journal Article

The traveling tournament problem: Improved algorithms based on cycle packing

• Jingyang Zhao
• Mingyu Xiao
• Chao Xu

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. In this paper, we investigate schedules for TTP-k and analyze the approximation ratio of the solutions. Most previous schedules were constructed based on a Hamiltonian cycle of the graph. We will propose a novel construction based on a k-cycle packing. Then, combining our k-cycle packing schedule with the Hamiltonian cycle schedule, we obtain improved approximation ratios for TTP-k with deep analysis. The case where k = 3, TTP-3, is one of the most investigated cases. We improve the approximation ratio of TTP-3 from ( 1. 667 + ε ) to ( 1. 598 + ε ), for any ε > 0. For TTP-4, we improve the approximation ratio from ( 1. 750 + ε ) to ( 1. 700 + ε ). By a refined analysis of the Hamiltonian cycle construction, we also improve the approximation ratio of TTP-k from ( 5 k − 7 2 k + ε ) to ( 5 k 2 − 4 k + 3 2 k ( k + 1 ) + ε ) for any constant k ≥ 5.

IJCAI Conference 2024 Conference Paper

A Better Approximation for Bipartite Traveling Tournament in Inter-League Sports Scheduling

• Jingyang Zhao
• Mingyu Xiao

The bipartite traveling tournament problem (BTTP) was initially introduced by Hoshino and Kawarabayashi (AAAI 2011) to address inter-league sports scheduling, which aims to design a feasible bipartite tournament between two n-team leagues under some constraints such that the total traveling distance of all participating teams is minimized. Since its introduction, several heuristic methods have been developed to design feasible schedules for NBA, NPB and so on. In terms of solution quality with a theoretical guarantee, previously only a (2+ε) approximation is known for the case that n≡0 (mod 3). Whether there are similar results for the cases that n≡1 (mod 3) and n≡2 (mod 3) was asked in the literature. In this paper, we answer this question positively by proposing a (3/2+ε)-approximation algorithm for any n and any constant ε>0, which also improves the previous ratio for the case that n≡0 (mod 3).

TCS Journal 2024 Journal Article

A deterministic approximation algorithm for metric triangle packing

• Jingyang Zhao
• Mingyu Xiao

Given an edge-weighted metric complete graph with n vertices, the maximum weight metric triangle packing problem is to find a set of n / 3 vertex-disjoint triangles with the total weight of all triangles in the packing maximized. Several simple methods can lead to a 2/3-approximation ratio. However, this barrier is not easy to break. Chen et al. proposed a randomized approximation algorithm with an expected ratio of ( 0. 66768 − ε ) for any constant ε > 0. In this paper, we improve the approximation ratio to ( 0. 66835 − ε ). Furthermore, we can derandomize our algorithm.

IJCAI Conference 2024 Conference Paper

A Fast Algorithm for MaxSAT above Half Number of Clauses

• Junqiang Peng
• Mingyu Xiao

We study the following parameterization of the MaxSAT problem: Given a CNF formula F with m clauses, decide whether at least m/2 + μ clauses in F could be satisfied, where μ is the excess of the number of satisfied clauses over the trivial lower bound m/2 and is taken as the parameter. This perspective is known as the "above guarantee" parameterization. Since its introduction by Mahajan and Raman [1999], the analysis of parameterization above guarantee has become a highly active and fruitful line of research. In this paper, we develop a new algorithm with runtime O*(2. 1479^μ), significantly improving the previous best upper bound O*(5. 4064^μ) for this important problem. Here, the O* notation omits polynomial factors.

AAAI Conference 2024 Conference Paper

A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem

• Lu Liu
• Mingyu Xiao
• Yi Zhou

The maximum vertex-weighted clique problem (MVWCP) and the maximum edge-weighted clique problem (MEWCP) are two natural extensions of the fundamental maximum clique problem. In this paper, we systematically study MEWCP and make the following major contributions: (1) We show that MEWCP is NP-hard even when the minimum degree of the graph is n-2, in contrast to MVWCP which is polynomial-time solvable when the minimum degree of the graph is at least n-3. This result distinguishes the complexity of the two problems for the first time. (2) To address MEWCP, we develop an efficient branch-and-bound algorithm called MEWCat with both practical and theoretical performance guarantees. In practice, MEWCat utilizes a new upper bound tighter than existing ones, which allows for more efficient pruning of branches. In theory, we prove a running-time bound of O*(1.4423^n) for MEWCat, which breaks the trivial bound of O*(2^n) in the research line of practical exact MEWCP solvers for the first time. (3) Empirically, we evaluate the performance of MEWCat on various benchmark instances. The experiments demonstrate that MEWCat outperforms state-of-the-art exact solvers significantly. For instance, on 16 DIMACS graphs that the state-of-the-art solver BBEWC fails to solve within 7200 seconds, MEWCat solves all of them with an average time of less than 1000 seconds. On real-world graphs, MEWCat achieves an average speedup of over 36x.

TCS Journal 2024 Journal Article

Exact algorithms for restricted subset feedback vertex set in chordal and split graphs

• Tian Bai
• Mingyu Xiao

The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = ( V, E ), a terminal set T ⊆ V, and an integer k as the input. The task is to determine whether there exists a subset S ⊆ V ∖ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP -complete even when the input graph is restricted to split graphs. In this paper, we mainly show that R-SFVS in chordal and split graphs can be solved in O ( 1. 1550 | V | ) time and exponential space or in O ( 1. 1605 | V | ) time and polynomial space, significantly improving all previous results. As a by-product, we show that the Maximum Independent Set problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to Vertex Cover, we obtain an O ⁎ ( 1. 2738 k ) -time parameterized algorithm and a tight O ( k 2 ) -kernel for R-SFVS in chordal and split graphs.

IJCAI Conference 2024 Conference Paper

Exactly Solving Minimum Dominating Set and Its Generalization

• Ziliang Xiong
• Mingyu Xiao

The Minimum Dominating Set Problem (MDSP) is an important NP-Hard optimization problem with many applications in various domains. This paper designs two exact algorithms for MDSP that use the same Branch-and-Bound framework. However, one uses LP relaxations as lower bounds for pruning the search space, and the other one is a pure combinatorial algorithm. The two algorithms possess a distinct advantage. Performance experiments on standard test datasets reveal that our combinatorial algorithm is over 1000 times faster than the previous state-of-the-art exact algorithm presented in IJCAI 2023, and our LP Relaxation algorithm can even enhance the speed of our combinatorial algorithm by over 100 times. However, our combinatorial algorithm still outperform the LP Relaxation algorithm on very dense graphs.

IJCAI Conference 2024 Conference Paper

Improved Approximation Algorithms for Capacitated Location Routing

• Jingyang Zhao
• Mingyu Xiao
• Shunwang Wang

The Capacitated Location Routing Problem is an important planning and routing problem in logistics, which generalizes the capacitated vehicle routing problem and the uncapacitated facility location problem. In this problem, we are given a set of depots and a set of customers where each depot has an opening cost and each customer has a demand, and we need to use minimum cost to open some depots and route capacitated vehicles in the opened depots to satisfy all customers' demand. In this paper, we propose a 4. 169-approximation algorithm for this problem, improving the best-known 4. 38-approximation ratio (Transportation Science 2013). Moreover, if the demand of each customer is allowed to be delivered by multiple tours, we propose a more refined 4. 092-approximation algorithm. Experimental study on benchmark instances shows that the quality of our computed solutions is better than that of previous algorithms and is also much closer to optimality than the provable approximation factor.

TCS Journal 2024 Journal Article

Kernelization for edge triangle packing and covering via a discharging method

• Zimo Sheng
• Mingyu Xiao

Edge Triangle Packing and Edge Triangle Covering are dual problems extensively studied in the field of parameterized complexity. Given a graph G and an integer k, Edge Triangle Packing seeks to determine whether there exists a set of at least k edge-disjoint triangles in G, while Edge Triangle Covering aims to find out whether there exists a set of at most k edges that intersects all triangles in G. Previous research has shown that Edge Triangle Packing has a kernel of ( 3 + ϵ ) k vertices, while Edge Triangle Covering has a kernel of 6k vertices. In this paper, we show that the two problems allow kernels of 3k vertices, improving all previous results. A significant contribution of our work is the utilization of a novel discharging method for analyzing kernel size, which exhibits potential for analyzing other kernel algorithms.

TCS Journal 2023 Journal Article

A 5k-vertex kernel for 3-path vertex cover

• Mingyu Xiao
• Shaowei Kou

A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices contains at least one vertex from C. The parameterized 3-path vertex cover problem asks whether a graph has a 3-path vertex cover of size at most k. We give a kernel of 5k vertices for this problem, improving the previously known bounds.

IJCAI Conference 2023 Conference Paper

A Fast Maximum k-Plex Algorithm Parameterized by the Degeneracy Gap

• Zhengren Wang
• Yi Zhou
• Chunyu Luo
• Mingyu Xiao

Given a graph, the k-plex is a vertex set in which each vertex is not adjacent to at most k-1 other vertices in the set. The maximum k-plex problem, which asks for the largest k-plex from a given graph, is an important but computationally challenging problem in applications like graph search and community detection. So far, there is a number of empirical algorithms without sufficient theoretical explanations on the efficiency. We try to bridge this gap by defining a novel parameter of the input instance, g_k(G), the gap between the degeneracy bound and the size of maximum k-plex in the given graph, and presenting an exact algorithm parameterized by g_k(G). In other words, we design an algorithm with running time polynomial in the size of input graph and exponential in g_k(G) where k is a constant. Usually, g_k(G) is small and bounded by O(log(|V|)) in real-world graphs, indicating that the algorithm runs in polynomial time. We also carry out massive experiments and show that the algorithm is competitive with the state-of-the-art solvers. Additionally, for large k values such as 15 and 20, our algorithm has superior performance over existing algorithms.

TCS Journal 2023 Journal Article

A parameterized algorithm for subset feedback vertex set in tournaments

• Tian Bai
• Mingyu Xiao

The Subset Feedback Vertex Set problem (SFVS) takes an n-vertex graph G = ( V, E ), a terminal set T ⊆ V, and an integer k as the input. The goal is to determine whether there exists a subset S ⊆ V of at most k vertices whose removal makes no terminal in T contained in a cycle in the remaining graph. When T = V, SFVS degenerates to the classical Feedback Vertex Set problem (FVS). Both SFVS and FVS have been extensively studied in parameterized algorithms. In this paper, we study parameterized algorithms for Subset Feedback Vertex Set in Tournaments (SFVST), i. e. , SFVS with the restriction that the input graph is always a tournament. By using the iterative compression method and a novel dynamic programming, we show that SFVST can be solved in 2 k + o ( k ) n O ( 1 ) time, improving the bound obtained from 3-Hitting Set.

AAAI Conference 2023 Conference Paper

Facility Location Games with Entrance Fees

• Mengfan Ma
• Mingyu Xiao
• Tian Bai
• Bakh Khoussainov

The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility's location. Thus, in our model, the cost of each agent is the sum of the distance to the facility and the entrance fee of the facility. The generalized model captures more real-life scenarios. In our model, the entrance fee function can be an arbitrary function, and the corresponding preferences of agents may not be single-peaked anymore: this makes the problem complex and requires new techniques in the analysis. We systematically study the model and design strategyproof mechanisms with nice approximation ratios and also complement these with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms, with respect to the utilitarian and egalitarian objectives. Most of our bounds are tight, and these bounds are independent of the entrance fee functions. Our results also match the results of the classical model.

IJCAI Conference 2023 Conference Paper

Fast Algorithms for SAT with Bounded Occurrences of Variables

• Junqiang Peng
• Mingyu Xiao

We present fast algorithms for the general CNF satisfiability problem (SAT) with running-time bound O*({c_d}^n), where c_d is a function of the maximum occurrence d of variables (d can also be the average occurrence when each variable appears at least twice), and n is the number of variables in the input formula. Similar to SAT with bounded clause lengths, SAT with bounded occurrences of variables has also been extensively studied in the literature. Especially, the running-time bounds for small values of d, such as d=3 and d=4, have become bottlenecks for algorithms evaluated by the formula length L and other algorithms. In this paper, we show that SAT can be solved in time O*(1. 1238^n) for d=3 and O*(1. 2628^n) for d=4, improving the previous results O*(1. 1279^n) and O*(1. 2721^n) obtained by Wahlström (SAT 2005) nearly 20 years ago. For d>=5, we obtain a running time bound of O*(1. 0641^{dn}), implying a bound of O*(1. 0641^L) with respect to the formula length L, which is also a slight improvement over the previous bound.

I&C Journal 2023 Journal Article

Further improvements for SAT in terms of formula length

• Junqiang Peng
• Mingyu Xiao

In this paper, we prove that the general CNF satisfiability problem can be solved in O ⁎ ( 1. 0638 L ) time, where L is the length of the input CNF-formula (i. e. , the total number of literals in the formula), which improves the previous result of O ⁎ ( 1. 0652 L ) obtained in 2009. Our algorithm was analyzed by using the measure-and-conquer method. Our improvements are mainly attributed to the following two points: we carefully design branching rules to deal with degree-5 and degree-4 variables to avoid previous bottlenecks; we show that some worst cases will not always happen, and then we can use an amortized technique to get further improvements. In our analyses, we provide some general frameworks for analysis and several lower bounds on the decreasing of the measure to simplify the arguments. These techniques may be used to analyze more algorithms based on the measure-and-conquer method.

AAMAS Conference 2023 Conference Paper

MMS Allocations of Chores with Connectivity Constraints: New Methods and New Results

• Mingyu Xiao
• Guoliang Qiu
• Sen Huang

We study the problem of allocating indivisible chores to agents under the Maximin share (MMS) fairness notion. The chores are embedded on a graph and each bundle of chores assigned to an agent should be connected. Although there is a simple algorithm for MMS allocations of goods on trees, it remains open whether MMS allocations of chores on trees always exist or not, which is a simple but annoying problem in chores allocation. In this paper, we introduce a new method for chores allocation with connectivity constraints, called the group-satisfied method, that can show the existence of MMS allocations of chores on several subclasses of trees. Even these subcases are non-trivial and our results can be considered as a significant step to the open problem. We also consider MMS allocations of chores on cycles where we get the tight approximation ratio for three agents. Our result was obtained via the linear programming (LP) method, which enables us not only to compute approximate MMS allocations but also to construct tight examples of the nonexistence of MMS allocations without complicated combinatorial analysis. These two proposed methods, the group-satisfied method and the LP method, have the potential to solve more related problems.

AAAI Conference 2023 Conference Paper

The Linear Distance Traveling Tournament Problem Allows an EPTAS

• Jingyang Zhao
• Mingyu Xiao

The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling and has been extensively studied in the field of AI. In this problem, we are going 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) under the constraint that each team can have at most k-consecutive home games or away games. The Linear Distance Traveling Tournament Problem (LDTTP-k), where all teams are located on a line, was introduced by Hoshino and Kawarabayashi (AAAI 2012). For LDTTP-3, they gave a 4/3-approximation algorithm for n≡4 (mod 6) teams. In this paper, we show that for any 3≤k=o(∛n), LDTTP-k allows an efficient polynomial-time approximation scheme (EPTAS).

TCS Journal 2023 Journal Article

Upper and lower bounds on approximating weighted mixed domination

• Mingyu Xiao

A mixed dominating set of a graph G = ( V, E ) is a mixed set D of vertices and edges, such that for every edge or vertex, if it is not in D, then it is adjacent or incident to at least one vertex or edge in D. The mixed domination problem is to find a mixed dominating set with a minimum cardinality. It has applications in system control and some other scenarios and it is NP-hard to compute an optimal solution. This paper studies approximation algorithms and hardness of the weighted mixed dominating set problem. The weighted version is a generalization of the unweighted version, where all vertices are assigned the same nonnegative weight w v and all edges are assigned the same nonnegative weight w e, and the question is to find a mixed dominating set with a minimum total weight. Although the mixed dominating set problem has a simple 2-approximation algorithm, few approximation results for the weighted version are known. The main contributions of this paper include: 1. for w e ≥ w v, a 2-approximation algorithm; 2. for w e ≥ 2 w v, inapproximability within ratio 1. 3606 unless P = N P and within ratio 2 under UGC; 3. for 2 w v > w e ≥ w v, inapproximability within ratio 1. 1803 unless P = N P and within ratio 1. 5 under UGC; 4. for w e < w v, inapproximability within ratio ( 1 − ϵ ) ln ⁡ | V | unless P = N P for any ϵ > 0.

IJCAI Conference 2022 Conference Paper

An Exact MaxSAT Algorithm: Further Observations and Further Improvements

• Mingyu Xiao

In the maximum satisfiability problem (MaxSAT), given a CNF formula with m clauses and n variables, we are asked to find an assignment of the variables to satisfy the maximum number of clauses. Chen and Kanj showed that this problem can be solved in O*(1. 3248^m) time (DAM 2004) and the running time bound was improved to O*(1. 2989^m) by Xu et al. (IJCAI 2019). In this paper, we further improve the result to O*(1. 2886^m). By using some new reduction and branching techniques we can avoid several bottlenecks in previous algorithms and get the improvement on this important problem.

TCS Journal 2022 Journal Article

An improved kernel for planar vertex-disjoint triangle packing

• Zimo Sheng
• Mingyu Xiao

Triangle Packing is an important NP-hard problem that has been well studied in exact and parameterized complexity. In this paper, we study kernelization of the Planar Vertex-Disjoint Triangle Packing problem, which is to check whether a given planar graph has k vertex-disjoint triangles. We prove a kernel of 141k vertices, improving the previous bound of 732k.

AAAI Conference 2022 Conference Paper

Multi-Unit Auction in Social Networks with Budgets

• Mingyu Xiao
• Yuchao Song
• Bakh Khoussainov

We study multi-unit auctions in social networks, where each buyer has a fixed budget and can spread the sale information to the network neighbors. We design a mechanism encouraging buyers to report their valuations truthfully and spread the sale information. Our design uses the idea of the clinching mechanism to decide the transaction price and can be viewed as a network version of the mechanism. Most of the previous clinching mechanisms search for the transaction prices by increasing the current price. Our mechanism directly computes the transaction prices in polynomial time. Furthermore, the mechanism applies a technique to iteratively activate new buyers in the network. This ensures utility preservations of the buyers and benefits the seller. We prove key properties of our mechanism, such as no-positive-transfers, individual rationality, incentive compatibility, non-wastefulness and social welfare preservation.

TCS Journal 2021 Journal Article

An improved upper bound for SAT

• Huairui Chu
• Mingyu Xiao
• Zhe Zhang

We show that the CNF satisfiability problem can be solved in O ⁎ ( 1. 2226 m ) time, where m is the number of clauses in the formula, improving the known upper bounds O ⁎ ( 1. 234 m ) given by Yamamoto 15 years ago and O ⁎ ( 1. 239 m ) given by Hirsch 22 years ago. By using an amortized technique and careful case analysis, we successfully avoid the bottlenecks in previous algorithms and get the improvement.

AAAI Conference 2021 Conference Paper

An Improved Upper Bound for SAT

• Huairui Chu
• Mingyu Xiao
• Zhe Zhang

We show that the CNF satisfiability problem can be solved O∗ (1. 2226m ) time, where m is the number of clauses in the formula, improving the known upper bounds O∗ (1. 234m ) given by Yamamoto 15 years ago and O∗ (1. 239m ) given by Hirsch 22 years ago. By using an amortized technique and careful case analysis, we successfully avoid the bottlenecks in previous algorithms and get the improvement.

AAAI Conference 2021 Conference Paper

Enhancing Balanced Graph Edge Partition with Effective Local Search

• Zhenyu Guo
• Mingyu Xiao
• Yi Zhou
• Dongxiang Zhang
• Kian-Lee Tan

Graph partition is a key component to achieve workload balance and reduce job completion time in parallel graph processing systems. Among the various partition strategies, edge partition has demonstrated more promising performance in power-law graphs than vertex partition and thereby has been more widely adopted as the default partition strategy by existing graph systems. The graph edge partition problem, which is to split the edge set into multiple balanced parts to minimize the total number of copied vertices, has been widely studied from the view of optimization and algorithms. In this paper, we study local search algorithms for this problem to further improve the partition results from existing methods. More specifically, we propose two novel concepts, namely adjustable edges and blocks. Based on these, we develop a greedy heuristic as well as an improved search algorithm utilizing the property of the max-flow model. To evaluate the performance of our algorithms, we first provide adequate theoretical analysis in terms of the approximation quality. We significantly improve the previously known approximation ratio for this problem. Then we conduct extensive experiments on a large number of benchmark datasets and stateof-the-art edge partition strategies. The results show that our proposed local search framework can further improve the quality of graph partition by a wide margin.

AAAI Conference 2021 Conference Paper

Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding

• Yi Zhou
• Shan Hu
• Mingyu Xiao
• Zhang-Hua Fu

In a graph, a k-plex is a vertex set in which every vertex is not adjacent to at most k vertices of this set. The maximum k-plex problem, which asks for the largest k-plex from the given graph, is a key primitive in a variety of real-world applications like community detection and so on. In the paper, we develop an exact algorithm, Maplex, for solving this problem in real world graphs practically. Based on the existing first-order and the novel second-order reduction rules, we design a powerful preprocessing method which efficiently removes redundant vertices and edges for Maplex. Also, the graph color heuristic is widely used for overestimating the maximum clique of a graph. For the first time, we generalize this technique for bounding the size of maximum k-plex in Maplex. Experiments are carried out to compare our algorithm with other state-of-the-art solvers on a wide range of publicly available graphs. Maplex outperforms all other algorithms on large real world graphs and is competitive with existing solvers on artificial dense graphs. Finally, we shed light on the effectiveness of each key component of Maplex.

IJCAI Conference 2021 Conference Paper

The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound

• Jingyang Zhao
• Mingyu Xiao

The Traveling Tournament Problem is a well-known benchmark problem in tournament timetabling, which asks us to design a schedule of home/away games of n teams (n is even) under some feasibility requirements such that the total traveling distance of all the n teams is minimized. In this paper, we study TTP-2, the traveling tournament problem where at most two consecutive home games or away games are allowed, and give an effective algorithm for n/2 being odd. Experiments on the well-known benchmark sets show that we can beat previously known solutions for all instances with n/2 being odd by an average improvement of 2. 66%. Furthermore, we improve the theoretical approximation ratio from 3/2+O(1/n) to 1+O(1/n) for n/2 being odd, answering a challenging open problem in this area.

AAAI Conference 2020 Conference Paper

Algorithms for Manipulating Sequential Allocation

• Mingyu Xiao
• Jiaxing Ling

Sequential allocation is a simple and widely studied mechanism to allocate indivisible items in turns to agents according to a pre-specified picking sequence of agents. At each turn, the current agent in the picking sequence picks its most preferred item among all items having not been allocated yet. This problem is well-known to be not strategyproof, i. e. , an agent may get more utility by reporting an untruthful preference ranking of items. It arises the problem: how to find the best response of an agent? It is known that this problem is polynomially solvable for only two agents and NP-complete for an arbitrary number of agents. The computational complexity of this problem with three agents was left as an open problem. In this paper, we give a novel algorithm that solves the problem in polynomial time for each fixed number of agents. We also show that an agent can always get at least half of its optimal utility by simply using its truthful preference as the response.

AAAI Conference 2020 Conference Paper

Enumerating Maximal k -Plexes with Worst-Case Time Guarantee

• Yi Zhou
• Jingwei Xu
• Zhenyu Guo
• Mingyu Xiao
• Yan Jin

The problem of enumerating all maximal cliques in a graph is a key primitive in a variety of real-world applications such as community detection and so on. However, in practice, communities are rarely formed as cliques due to data noise. Hence, k-plex, a subgraph in which any vertex is adjacent to all but at most k vertices, is introduced as a relaxation of clique. In this paper, we investigate the problem of enumerating all maximal k-plexes and present FaPlexen, an enumeration algorithm which integrates the “pivot” heuristic and new branching schemes. To our best knowledge, for the first time, FaPlexen lists all maximal k-plexes with provably worst-case running time O(n2 γn ) in a graph with n vertices, where γ < 2. Then, we propose another algorithm CommuPlex which non-trivially extends FaPlexen to find all maximal kplexes of prescribed size for community detection in massive real-life networks. We finally carry out experiments on both real and synthetic graphs and demonstrate that our algorithms run much faster than the state-of-the-art algorithms.

AAAI Conference 2020 Conference Paper

Finding Minimum-Weight Link-Disjoint Paths with a Few Common Nodes

• Binglin Tao
• Mingyu Xiao
• Jingyang Zhao

Network survivability has drawn certain interest in network optimization. However, the demand for full protection of a network is usually too restrictive. To overcome the limitation of geographical environments and to save network resources, we turn to establish backup networks allowing a few common nodes. It comes out the problem of finding k link-disjoint paths between a given pair of source and sink in a network such that the number of common nodes shared by at least two paths is bounded by a constant and the total link weight of all paths is minimized under the above constraints. For the case k = 2, where we have only one backup path, several fast algorithms have been developed in the literature. For the case k > 2, little results are known. In this paper, we first establish the NP-hardness of the problem with general k. Motivated by the situation that each node in a network may have a capability of multicasting, we also study a restricted version with one more requirement that each node can be shared by at most two paths. For the restricted version, we build an ILP model and design a fast algorithm by using the techniques of augmenting paths and splitting nodes. Furthermore, experimental results on synthetic and real networks show that our algorithm is effective in practice.

TCS Journal 2020 Journal Article

Improved parameterized algorithms and kernels for mixed domination

• Mingyu Xiao
• Zimo Sheng

A mixed domination of a graph G = ( V, E ) is a mixed set D of vertices and edges such that for every edge or vertex, if it is not in D, then it is adjacent or incident to at least one vertex or edge in D. The Mixed Domination problem is to check whether there is a mixed domination of size at most k in a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of O ⁎ ( 4. 172 k ), which improves the previous bound of O ⁎ ( 7. 465 k ). For kernelization, it is known that the problem parameterized by k in general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernel by giving a kernel of 11 k − 16 vertices.

JAAMAS Journal 2020 Journal Article

Object reachability via swaps under strict and weak preferences

• Sen Huang
• Mingyu Xiao

Abstract The Housing Market problem is a widely studied resource allocation problem. In this problem, each agent can only receive a single object and has preferences over all objects. Starting from an initial endowment, we want to reach a certain assignment via a sequence of rational trades. We first consider whether an object is reachable for a given agent under a social network, where a trade between two agents is allowed if they are neighbors in the network and no participant has a deficit from the trade. Assume that the preferences of the agents are strict (no tie among objects is allowed). This problem is polynomial-time solvable in a star-network and NP-complete in a tree-network. It is left as a challenging open problem whether the problem is polynomial-time solvable when the network is a path. We answer this open problem positively by giving a polynomial-time algorithm. Then we show that when the preferences of the agents are weak (ties among objects are allowed), the problem becomes NP-hard when the network is a path and can be solved in polynomial time when the network is a star. Besides, we consider the computational complexity of finding different optimal assignments for the problem in the special case where the network is a path or a star.

TCS Journal 2020 Journal Article

Parameterized algorithms and kernels for almost induced matching

• Mingyu Xiao
• Shaowei Kou

The Almost Induced Matching problem asks whether we can delete at most k vertices from the input graph such that each vertex in the remaining graph has a degree exactly one. This paper studies parameterized algorithms for this problem by taking the size k of the deletion set as the parameter. We give a 7k-vertex kernel and an O ⁎ ( 1. 7485 k ) -time and polynomial-space algorithm, both of which are the best-known results. The linear-vertex kernel is obtained by using an extended crown decomposition and careful analysis, and the parameterized algorithm is based on a branch-and-search paradigm.

IJCAI Conference 2019 Conference Paper

Balanced Clustering: A Uniform Model and Fast Algorithm

• Weibo Lin
• Zhu He
• Mingyu Xiao

Clustering is a fundamental research topic in data mining and machine learning. In addition, many specific applications demand that the clusters obtained be balanced. In this paper, we present a balanced clustering model that is to minimize the sum of squared distances to cluster centers, with uniform regularization functions to control the balance degree of the clustering results. To solve the model, we adopt the idea of the k-means method. We show that the k-means assignment step has an equivalent minimum cost flow formulation when the regularization functions are all convex. By using a novel and simple acceleration technique for the k-means and network simplex methods our model can be solved quite efficiently. Experimental results over benchmarks validate the advantage of our algorithm compared to the state-of-the-art balanced clustering algorithms. On most datasets, our algorithm runs more than 100 times faster than previous algorithms with a better solution.

TCS Journal 2019 Journal Article

Frontiers in Algorithmics

• Mingyu Xiao
• Frances A. Rosamond

AAAI Conference 2019 Conference Paper

Object Reachability via Swaps along a Line

• Sen Huang
• Mingyu Xiao

The HOUSING MARKET problem is a widely studied resources allocation problem. In this problem, each agent can only receive a single object and has preferences over all objects. Starting from an initial endowment, we want to reach a certain assignment via a sequence of rational trades. We consider the problem whether an object is reachable for a given agent under a social network, where a trade between two agents is allowed if they are neighbors in the network and no participant has a deficit from the trade. Assume that the preferences of the agents are strict (no tie is allowed). This problem is polynomially solvable in a star-network and NPcomplete in a tree-network. It is left as a challenging open problem whether the problem is polynomially solvable when the network is a path. We answer this open problem positively by giving a polynomial-time algorithm. Furthermore, we show that the problem on a path will become NP-hard when the preferences of the agents are weak (ties are allowed).

AAMAS Conference 2018 Conference Paper

A Geometric Least Squares Method for Peer Assessment

• Mingyu Xiao
• Yuqing Wang
• Binglin Tao

In the peer assessment problem, a set of agents give evaluations to each other, and we are going to combine these peer assessments together to construct an overall evaluation. In this paper, we propose a geometric least squares method (GLS) to find an aggregate scoring overall agents for the peer assessment problem. Our method is based on the following observation. Since each agent has a missing score that should be given by itself, we consider the missing score as a variable and then each agent can be regarded as a line in an n-dimensional vector space. The final aggregate scores of the agents can be regarded as points on a line vector, called the projection vector. Thus, we treat the peer assessment problem as an optimization problem of selecting a projection vector with minimum total squared distance to all the lines representing the agents. We will see that this aggregate method has some advantages compared with the simple average method. One advantage is that, when the scores given by each agent (even ignoring the magnitude of the agent) are close to a groundtruth, the new method finds the groundtruth with the highest expectation.

IJCAI Conference 2018 Conference Paper

Exact Algorithms and Complexity of Kidney Exchange

• Mingyu Xiao
• Xuanbei Wang

Kidney Exchange is an approach to donor kidney transplantation where patients with incompatible donors swap kidneys to receive a compatible kidney. Since it was first put forward in 1986, increasing amount of people have gotten a life-saving kidney with the popularity of Kidney Exchange, as patients have more opportunities to get saved in this way. This growth is making the problem of optimally matching patients to donors more difficult to solve. The central problem, indeed, is the NP-hard problem to find the largest vertex-disjoint packing of cycles and chains in a graph that represents the compatibility between patients and donors, where due to the human resource limitation we may have constraints on the maximum length of cycles and chains. This paper mainly contributes to algorithms from theory for this problem with and without length constraints (restricted and free versions). We give: 1. A single-exponential exact algorithm based on subset convolution for the two versions; 2. An FPT algorithm for the free version with parameter being the number of vertex ``types'' in the graph.

AAAI Conference 2017 Conference Paper

A Fast Algorithm to Compute Maximum k-Plexes in Social Network Analysis

• Mingyu Xiao
• Weibo Lin
• Yuanshun Dai
• Yifeng Zeng

A clique model is one of the most important techniques on the cohesive subgraph detection; however, its applications are rather limited due to restrictive conditions of the model. Hence much research resorts to k-plex - a graph in which any vertex is adjacent to all but at most k vertices - which is a relaxation model of the clique. In this paper, we study the maximum k-plex problem and propose a fast algorithm to compute maximum k-plexes by exploiting structural properties of the problem. In an n-vertex graph, the algorithm computes optimal solutions in cn nO(1) time for a constant c < 2 depending only on k. To the best of our knowledge, this is the first algorithm that breaks the trivial theoretical bound of 2n for each k ≥ 3. We also provide experimental results over multiple real-world social network instances in support.

TCS Journal 2017 Journal Article

Complexity and kernels for bipartition into degree-bounded induced graphs

• Mingyu Xiao
• Hiroshi Nagamochi

In this paper, we study the parameterized complexity of the problems of partitioning the vertex set of a graph into two parts V A and V B such that V A induces a graph with degree at most a (resp. , an a-regular graph) and V B induces a graph with degree at most b (resp. , a b-regular graph). These two problems are called Upper-Degree-Bounded Bipartition and Regular Bipartition, respectively. When a = b = 0, the two problems become the polynomially solvable problem of checking the bipartition of a graph. When a = 0 and b = 1, Regular Bipartition becomes a well-known NP-hard problem, called Dominating Induced Matching. In this paper, firstly we prove that the two problems are NP-complete with any nonnegative integers a and b except a = b = 0. Secondly, we show the fixed-parameter tractability of these two problems with parameter k = | V A | being the size of one part of the bipartition by deriving several problem kernels for them and constrained versions of them.

I&C Journal 2017 Journal Article

Exact algorithms for maximum independent set

• Mingyu Xiao
• Hiroshi Nagamochi

We show that the maximum independent set problem on an n-vertex graph can be solved in 1. 1996 n n O ( 1 ) time and polynomial space, which even is faster than Robson's 1. 2109 n n O ( 1 ) -time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of 1. 1893 n n O ( 1 ) and 1. 1970 n n O ( 1 ), respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analysis on the structure of bounded-degree graphs.

I&C Journal 2017 Journal Article

Exact algorithms for Maximum Induced Matching

• Mingyu Xiao
• Huan Tan

This paper studies exact algorithms for the Maximum Induced Matching problem, in which an n-vertex graph is given and we are asked to find a set of maximum number of edges in the graph such that no pair of edges in the set have a common endpoint or are adjacent by another edge. This problem has applications in many different areas. We give several structural properties of the problem and show that the problem can be solved in O ⁎ ( 1. 4231 n ) time and polynomial space or O ⁎ ( 1. 3752 n ) time and exponential space.

TCS Journal 2017 Journal Article

Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems

• Mingyu Xiao
• Shaowei Kou

A dissociation set in a graph G = ( V, E ) is a vertex subset D such that the subgraph G [ D ] induced on D has vertex degree at most 1. A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices contains at least one vertex from C. A vertex set D is a dissociation set if and only if V ∖ D is a 3-path vertex cover. There are many applications for dissociation sets and 3-path vertex covers. However, it is NP-hard to compute a dissociation set of maximum size or a 3-path vertex cover of minimum size in graphs. Several exact algorithms have been proposed for these two problems and they can be solved in O ⁎ ( 1. 4658 n ) time in n-vertex graphs. In this paper, we reveal some interesting structural properties of the two problems, which allow us to solve them in O ⁎ ( 1. 4656 n ) time and polynomial space or O ⁎ ( 1. 3659 n ) time and exponential space.

IJCAI Conference 2017 Conference Paper

Score Aggregation via Spectral Method

• Mingyu Xiao
• Yuqing Wang

The score aggregation problem is to find an aggregate scoring over all candidates given individual scores provided by different agents. This is a fundamental problem with a broad range of applications in social choice and many other areas. The simple and commonly used method is to sum up all scores of each candidate, which is called the sum-up method. In this paper, we give good algebraic and geometric explanations for score aggregation, and develop a spectral method for it. If we view the original scores as `noise data', our method can find an `optimal' aggregate scoring by minimizing the `noise information'. We also suggest a signal-to-noise indicator to evaluate the validity of the aggregation or the consistency of the agents.

TCS Journal 2014 Journal Article

A refined exact algorithm for Edge Dominating Set

• Mingyu Xiao
• Hiroshi Nagamochi

In this paper, we present a new exact algorithm for the Edge Dominating Set problem, and analyze its running time by the Measure and Conquer method. Our algorithm runs in 1. 3160 n n O ( 1 ) time for a graph with n vertices, which is the currently fastest known time for the Edge Dominating Set problem. By designing new branching rules based upon conceptually simple local structures, which we call clique-producing vertices and cycles, we obtain an algorithm that is simpler than the previously fastest known algorithm and has an improved time bound as well.

TCS Journal 2013 Journal Article

Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs

• Mingyu Xiao
• Hiroshi Nagamochi

We present an O ∗ ( 1. 083 6 n ) -time algorithm for finding a maximum independent set in an n -vertex graph with degree bounded by 3, which improves all previous running time bounds for this problem. Our approach has the following two features. Without increasing the number of reduction/branching rules to get an improved time bound, we first successfully extract the essence from the previously known reduction rules such as domination, which can be used to get simple algorithms. More formally, we introduce a procedure for computing “confining sets”, which unifies several known reducible subgraphs and covers new reducible subgraphs. Second we identify those instances that generate the worst recurrence among all recurrences of our branching rules as “bottleneck instances” and prove that bottleneck instances cannot appear consecutively after each branching operation.

TCS Journal 2013 Journal Article

FPTASs for trimming weighted trees

• Mingyu Xiao
• Takuro Fukunaga
• Hiroshi Nagamochi

Given a tree with nonnegative edge cost and nonnegative vertex weight, and a number k ≥ 0, we consider the following four cut problems: cutting vertices of weight at most or at least k from the tree by deleting some edges such that the remaining part of the graph is still a tree and the total cost of the edges being deleted is minimized or maximized. The MinMstCut problem (cut vertices of weight at most k and minimize the total cost of the edges being deleted) can be solved in linear time and space and the other three problems are NP-hard. In this paper, we design an O ( n l / ε ) -time O ( l 2 / ε + n ) -space algorithm for MaxMstCut, and O ( n l ( 1 / ε + log n ) ) -time O ( l 2 / ε + n ) -space algorithms for the other two problems, MinLstCut and MaxLstCut, where n is the number of vertices in the tree, l the number of leaves, and ε > 0 the prescribed error bound.

TCS Journal 2013 Journal Article

New parameterized algorithms for the edge dominating set problem

• Mingyu Xiao
• Ton Kloks
• Sheung-Hung Poon

An edge dominating set of a graph G = ( V, E ) is a subset M ⊆ E of edges in the graph such that each edge in E − M is incident with at least one edge in M. In an instance of the parameterized edge dominating set problem, we are given a graph G = ( V, E ) and an integer k, and we are asked to decide whether G has an edge dominating set of size at most k. In this paper, we show that the parameterized edge dominating set problem can be solved in O ∗ ( 2. 314 7 k ) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O ( k 3 ) edges.

TCS Journal 2013 Journal Article

Parameterized edge dominating set in graphs with degree bounded by 3

• Mingyu Xiao
• Hiroshi Nagamochi

In this paper, we present an O ∗ ( 2. 147 9 k ) -time algorithm to decide whether a graph of maximum degree 3 has an edge dominating set of size at most k or not, which is based on enumeration of vertex covers and improves all previous results on this problem. We first enumerate partial vertex covers of size at most 2 k and then construct an edge dominating set based on each vertex cover to find a required edge dominating set. To effectively enumerate vertex covers, we adopt a branch-and-reduce method, and use some techniques, such as ‘pseudo-cliques’ and ‘amortized transfer of cliques, ’ to analyze the running time bound.