Author name cluster

Chaoyi Wang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

TCS Journal 2013 Journal Article

Feedback vertex sets on restricted bipartite graphs

Wei Jiang
Tian Liu
Chaoyi Wang
Ke Xu

A feedback vertex set (FVS) in a graph is a subset of vertices whose complement induces a forest. Finding a minimum FVS is NP -complete on bipartite graphs, but tractable on convex bipartite graphs and on chordal bipartite graphs. A bipartite graph is called tree convex, if a tree is defined on one part of the vertices, such that for every vertex in the other part, its neighborhood induces a subtree. When the tree is a path, a triad or a star, the bipartite graph is called convex bipartite, triad convex bipartite or star convex bipartite, respectively. We show that: (1) FVS is tractable on triad convex bipartite graphs; (2) FVS is NP -complete on star convex bipartite graphs and on tree convex bipartite graphs where the maximum degree of vertices on the tree is at most three.

Details DOI

IJCAI Conference 2011 Conference Paper

Large Hinge Width on Sparse Random Hypergraphs

Tian Liu
Xiaxiang Lin
Chaoyi Wang
Kaile Su
Ke Xu

Consider random hypergraphs on n vertices, where each k-element subset of vertices is selected with probability p independently and randomly as a hyperedge. By sparse we mean that the total number of hyperedges is O(n) or O(n ln n). When k = 2, these are exactly the classical Erdö s-Ré nyi random graphs G(n, p). We prove that with high probability, hinge width on these sparse random hypergraphs can grow linearly with the expected number of hyperedges. Some random constraint satisfaction problems such as Model RB and Model RD have satisfiability thresholds on these sparse constraint hypergraphs, thus the large hinge width results provide some theoretical evidence for random instances around satisfiability thresholds to be hard for a standard hinge-decomposition based algorithm. We also conduct experiments on these and other kinds of random graphs with several hundreds vertices, including regular random graphs and power law random graphs. The experimental results also show that hinge width can grow linearly with the number of edges on these different random graphs. These results may be of further interests.

PDF Details DOI