[Back]

L. Bulteau, N. Grüttemeier, C. Komusiewicz, M. Sorge:
"Your rugby mates don´t need to know your colleagues: Triadic closure with edgecolors";
Journal of Computer and System Sciences, 120 (2021), 75 - 96.

Given an undirected graph G =(V, E)the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edges as weak and strong such that at most kedges are weak and for each induced P3in Gat least one edge is weak. We study the following generalizations of STC with cdifferent strong edge colors. In Multi-STC an induced P3may receive two strong labels as long as they are different. In Edge-List Multi-STC and Vertex-List Multi-STC we may restrict the set of permitted colors for 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 2o(|V|2). We proceed with a parameterized complexity analysis in which we extend previous algorithms and kernelizations for STC [11,14]to the three variants or outline the limits of such an extension.
©

http://dx.doi.org/10.1016/j.jcss.2021.03.001

https://publik.tuwien.ac.at/files/publik_300338.pdf