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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given an undirected graph $G=(V,E)$ the NP-hard Strong Triadic Closure (STC)problem asks for a labeling of the edges as \emph{weak} and \emph{strong} suchthat at most $k$ edges are weak and for each induced $P_3$ in $G$ at least oneedge is weak. In this work, we study the following generalizations of STC with$c$ different strong edge colors. In Multi-STC an induced $P_3$ may receive twostrong labels as long as they are different. In Edge-List Multi-STC andVertex-List Multi-STC we may additionally restrict the set of permitted colorsfor each edge of $G$. We show that, under the Exponential Time Hypothesis(ETH), Edge-List Multi-STC and Vertex-List Multi-STC cannot be solved in time$2^{o(|V|^2)}$. We then proceed with a parameterized complexity analysis inwhich we extend previous fixed-parameter tractability results andkernelizations for STC [Golovach et al., Algorithmica '20, Gr\"uttemeier andKomusiewicz, Algorithmica '20] to the three variants with multiple edge colorsor outline the limits of such an extension.

Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge Colors