English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In this paper we investigate the colorful components framework, motivated byapplications emerging from comparative genomics. The general goal is to removea collection of edges from an undirected vertex-colored graph $G$ such that inthe resulting graph $G'$ all the connected components are colorful (i.e., anytwo vertices of the same color belong to different connected components). Wewant $G'$ to optimize an objective function, the selection of this functionbeing specific to each problem in the framework.  We analyze three objective functions, and thus, three different problems,which are believed to be relevant for the biological applications: minimizingthe number of singleton vertices, maximizing the number of edges in thetransitive closure, and minimizing the number of connected components.  Our main result is a polynomial time algorithm for the first problem. Thisresult disproves the conjecture of Zheng et al. that the problem is $ NP$-hard(assuming $P \neq NP$). Then, we show that the second problem is $ APX$-hard,thus proving and strengthening the conjecture of Zheng et al. that the problemis $ NP$-hard. Finally, we show that the third problem does not admitpolynomial time approximation within a factor of $|V|^{1/14 - \epsilon}$ forany $\epsilon > 0$, assuming $P \neq NP$ (or within a factor of $|V|^{1/2 -\epsilon}$, assuming $ZPP \neq NP$).

Algorithmic and Hardness Results for the Colorful Components Problems