Jed Yang::Papers

J. Yang, Some NP-complete edge packing and partitioning problems in planar graphs, Communications on Number Theory and Combinatorial Theory 3 (2022), Article 2.
Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bernáth and Király proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of determining whether the edge set of a graph can be partitioned into a spanning tree and a (not-necessarily spanning) tree. We prove that all three problems remain NP-complete even when restricted to planar graphs.
(with P. Pylyavskyy) Puzzles in K-homology of Grassmannians, Pacific Journal of Mathematics 303 (2019), 703–727.
Knutson, Tao, and Woodward formulated a Littlewood–Richardson rule for the cohomology ring of Grassmannians in terms of puzzles. Vakil and Wheeler–Zinn-Justin have found additional triangular puzzle pieces that allow one to express structure constants for K-theory of Grassmannians. Here we introduce two other puzzle pieces of hexagonal shape, each of which gives a Littlewood–Richardson rule for K-homology of Grassmannians. We also explore the corresponding eight versions of K-theoretic Littlewood–Richardson tableaux.
(with N. M. Tran) Antibiotics Time Machine is NP-hard, AMS Notices 64 (2017), 1136–1140.
The antibiotics time machine is an optimization question posed by Mira et al. on the design of antibiotic treatment plans to minimize antibiotic resistance. The problem is a variation of the Markov decision process. These authors asked if the problem can be solved efficiently. In this paper, we show that this problem is NP-hard in general.
(with D. Davis, V. Dods, C. Traub) Geodesics on the regular tetrahedron and the cube, Discrete Mathematics 340 (2017), 3183–3196.
Consider all geodesics between two given points on a polyhedron. On the regular tetrahedron, we describe all the geodesics from a vertex to a point, which could be another vertex. Using the Stern–Brocot tree to explore the recursive structure of geodesics between vertices on a cube, we prove, in some precise sense, that there are twice as many geodesics between certain pairs of vertices than other pairs. We also obtain the fact that there are no geodesics that start and end at the same vertex on the regular tetrahedron or the cube.
(with I. Pak) Tiling with puzzle pieces is hard, in preparation.
(with G.-Y. Pan, J.-Y. Jou, B.-C. Lai) Scalable global power management policy based on combinatorial optimization for multiprocessors, ACM Transactions on Embedded Computing Systems 14 (2015), Article 70, 24pp.
J. Yang, Rectangular tileability and complementary tileability are undecidable, European Journal of Combinatorics 41 (2014), 20–34.
Does a given set of polyominoes tile some rectangle? We show that this problem is undecidable. In a different direction, we also consider tiling a cofinite subset of the plane. The tileability is undecidable for many variants of this problem. However, we present an algorithm for testing whether the complement of a finite region is tileable by a set of rectangles.
J. Yang, Computational complexity and decidability of tileability, PhD dissertation (2013).
For finite polyomino regions, tileability by a pair of rectangles is NP-complete for all but trivial cases yet can be solved in quadratic time for simply connected regions. Through a series of reductions and improvements, we construct a set of 117 rectangles for which the tileability of simply connected regions is NP-complete.
Tiling by dominoes in the plane is a matching problem, and thus can be solved in polynomial time. While the decision problem remains polynomial in higher dimensions, we prove that the counting problem becomes #P-complete. We also establish NP- and #P-completeness results for another generalization of domino tilings to higher dimensions.
We show that tileability of cofinite regions is undecidable, even for some fixed set of tiles, but present an algorithm for solving the case where all tiles are rectangular. We also show that whether a finite region can be enlarged by tiles such that the resulting region becomes tileable is also undecidable. Moreover, the existence of a tileable rectangle by a set of polyominoes is also shown to be undecidable.
It is not surprising that tiles can emulate other computational systems such as Turing machines and cellular automata. Some of these connections and consequences are explored and outlined. In particular, there are conjectures in the theory of cellular automata that, if proved, could lead to improvements of results in the theory of tilings.
(with I. Pak) The complexity of generalized domino tilings, The Electronic Journal of Combinatorics 20 (2013), P12, 23pp.
Tiling planar regions with dominoes is a classical problem, where the decision and counting problems are polynomial. We prove a variety of hardness results (both NP- and #P-completeness) for different generalizations of dominoes in three and higher dimensions.
(with I. Pak) Tiling simply connected regions with rectangles, Journal of Combinatorial Theory, Ser. A 120 (2013), 1804–1816.
In 1995, Beauquier, Nivat, Rémila, and Robson showed that tiling of general regions with two rectangles is NP-complete, except for a few trivial special cases. In a different direction, in 2005, Rémila showed that for simply connected regions by two rectangles, the tileability can be solved in quadratic time (in the area). We prove that there is a finite set of at most 10⁶ rectangles for which the tileability problem of simply connected regions is NP-complete, closing the gap between positive and negative results in the field. We also prove that counting such rectangular tilings is #P-complete, a first result of this kind.

Note: The above version is essentially identical to the arXiv version. The journal version is somewhat abridged at the journal's request. Notably, it is missing the original proof of Lemma 3.2, which is replaced with a UTM argument.
J. Yang's thesis contains expanded definitive versions of both, with constants substantially improved.
J. Yang, Vertex-pancyclicity of hypertournaments, Journal of Graph Theory 63 (2010), 338–348.
A hypertournament, or a k-tournament, on n vertices, 2 ≤ k ≤ n, is a pair T = (V, E), where the vertex set V is a set of size n and the edge set E is the collection of all possible subsets of size k of V, called the edges, each taken in one of its k! possible permutations. A k-tournament is vertex-pancyclic if each vertex is contained in (directed) cycles of all possible lengths. A k-tournament is strong if there is a path from u to v for each pair of distinct vertices u and v. We examine the question posed by Gutin and Yeo about the characterization of vertex-pancyclic hypertournaments. We utilize the majority digraph to reduce a k-tournament to an ordinary tournament (2-tournament). We employ this method to extend Moon's theorem (a tournament is vertex-pancyclic if and only if it is strong) to hypertournaments. We prove that for a k-tournament on n vertices, if k ≥ 8 and n ≥ k + 3, then it is vertex-pancyclic if and only if it is strong. The same conclusion holds if k ≥ 5 and n ≥ k + 4, or if k = 4 and n ≥ 11, or if k = 3 and n ≥ 15. We also find bounds for the generalized problem when we extend vertex-pancyclicity to require d edge-disjoint cycles of each possible length and extend strong connectivity to require d edge-disjoint paths between each pair of vertices. Our results include and extend that of Petrovic and Thomassen.