BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mingyu Xiao

Mingyu Xiao appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational ComplexityDiscrete MathematicsArtificial IntelligenceComputer Science and Game Theorymath.CO

Catalog footprint

What is connected

12works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2026arXiv

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

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 \textsc{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 $\ell$). A natural question is that: can TFP be efficiently solved when $k$ or $\ell$ 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 \textsc{Tournament Fixing} problem.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem

The Multiple-Depot Split Delivery Vehicle Routing Problem (MD-SDVRP) is a challenging problem with broad applications in logistics. The goal is to serve customers' demand using a fleet of capacitated vehicles located in multiple depots, where each customer's demand can be served by more than one vehicle, while minimizing the total travel cost of all vehicles. We study approximation algorithms for this problem. Previously, the only known result was a $6$-approximation algorithm for a constant number of depots (INFORMS J. Comput. 2023), and whether this ratio could be improved was left as an open question. In this paper, we resolve it by proposing a $(6-2\cdot 10^{-36})$-approximation algorithm for this setting. Moreover, we develop constant-factor approximation algorithms that work beyond a constant number of depots, improved parameterized approximation algorithms related to the vehicle capacity and the number of depots, as well as bi-factor approximation algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Further Improvements for SAT in Terms of Formula Length

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Object Reachability via Swaps under Strict and Weak Preferences

The \textsc{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 polynomially solvable in a star-network and NP-complete 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. Then we show that when the preferences of the agents are weak (ties among objects are allowed), the problem becomes NP-hard even when the network is a path. In addition, we consider the computational complexity of finding different optimal assignments for the problem under the network being a path or a star.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Complexity of the Partition Coloring Problem

Given a simple undirected graph $G=(V,E)$ and a partition of the vertex set $V$ into $p$ parts, the \textsc{Partition Coloring Problem} asks if we can select one vertex from each part of the partition such that the chromatic number of the subgraph induced on the $p$ selected vertices is bounded by $k$. PCP is a generalized problem of the classical \textsc{Vertex Coloring Problem} and has applications in many areas, such as scheduling and encoding etc. In this paper, we show the complexity status of the \textsc{Partition Coloring Problem} with three parameters: the number of colors, the number of parts of the partition, and the maximum size of each part of the partition. Furthermore, we give a new exact algorithm for this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Characterizing Star-PCGs

A graph $G$ is called a pairwise compatibility graph (PCG, for short) if it admits a tuple $(T,w, d_{\min},d_{\max})$ of a tree $T$ whose leaf set is equal to the vertex set of $G$, a non-negative edge weight $w$, and two non-negative reals $d_{\min}\leq d_{\max}$ such that $G$ has an edge between two vertices $u,v\in V$ if and only if the distance between the two leaves $u$ and $v$ in the weighted tree $(T,w)$ is in the interval $[d_{\min}, d_{\max}]$. The tree $T$ is also called a witness tree of the PCG $G$. The problem of testing if a given graph is a PCG is not known to be NP-hard yet. To obtain a complete characterization of PCGs is a wide open problem in computational biology and graph theory. In literature, most witness trees admitted by known PCGs are stars and caterpillars. In this paper, we give a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Some Reduction Operations to Pairwise Compatibility Graphs

A graph $G=(V,E)$ with a vertex set $V$ and an edge set $E$ is called a pairwise compatibility graph (PCG, for short) if there are a tree $T$ whose leaf set is $V$, a non-negative edge weight $w$ in $T$, and two non-negative reals $d_{\min}\leq d_{\max}$ such that $G$ has an edge $uv\in E$ if and only if the distance between $u$ and $v$ in the weighted tree $(T,w)$ is in the interval $[d_{\min}, d_{\max}]$. PCG is a new graph class motivated from bioinformatics. In this paper, we give some necessary and sufficient conditions for PCG based on cut-vertices and twins, which provide reductions among PCGs. Our results imply that complete $k$-partite graph, cactus, and some other graph classes are subsets of PCG.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Linear-time Algorithm for Integral Multiterminal Flows in Trees

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 $Ω(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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Parameterized Algorithm for Bounded-Degree Vertex Deletion

The $d$-bounded-degree vertex deletion problem, to delete at most $k$ vertices in a given graph to make the maximum degree of the remaining graph at most $d$, finds applications in computational biology, social network analysis and some others. It can be regarded as a special case of the $(d+2)$-hitting set problem and generates the famous vertex cover problem. The $d$-bounded-degree vertex deletion problem is NP-hard for each fixed $d\geq 0$. In terms of parameterized complexity, the problem parameterized by $k$ is W[2]-hard for unbounded $d$ and fixed-parameter tractable for each fixed $d\geq 0$. Previously, (randomized) parameterized algorithms for this problem with running time bound $O^*((d+1)^k)$ are only known for $d\leq2$. In this paper, we give a uniform parameterized algorithm deterministically solving this problem in $O^*((d+1)^k)$ time for each $d\geq 3$. Note that it is an open problem whether the $d'$-hitting set problem can be solved in $O^*((d'-1)^k)$ time for $d'\geq 3$. Our result answers this challenging open problem affirmatively for a special case. Furthermore, our algorithm also gets a running time bound of $O^*(3.0645^k)$ for the case that $d=2$, improving the previous deterministic bound of $O^*(3.24^k)$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On a generalization of Nemhauser and Trotter's local optimization theorem

Fellows, Guo, Moser and Niedermeier~[JCSS2011] proved a generalization of Nemhauser and Trotter's theorem, which applies to \textsc{Bounded-Degree Vertex Deletion} (for a fixed integer $d\geq 0$, to delete $k$ vertices of the input graph to make the maximum degree of it $\leq d$) and gets a linear-vertex kernel for $d=0$ and $1$, and a superlinear-vertex kernel for each $d\geq 2$. It is still left as an open problem whether \textsc{Bounded-Degree Vertex Deletion} admits a linear-vertex kernel for each $d\geq 3$. In this paper, we refine the generalized Nemhauser and Trotter's theorem and get a linear-vertex kernel for each $d\geq 0$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

New parameterized algorithms for edge dominating set

An edge dominating set of a graph G=(V,E) is a subset M 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.3147^k) time and polynomial space. We show that this problem can be reduced to a quadratic kernel with O(k^3) edges.

0 citations0 reviewsNo code linkedOpen access