Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge Colors
share
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 k edges are weak and for each induced P_3 in G at least one edge 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 two strong labels as long as they are different. In Edge-List Multi-STC and Vertex-List Multi-STC we may additionally restrict the set of permitted colors for each edge of G. We show that, under the ETH, Edge-List Multi-STC and Vertex-List Multi-STC cannot be solved in time 2^o(|V|^2), and that Multi-STC is NP-hard for every fixed c. We then proceed with a parameterized complexity analysis in which we extend previous fixed-parameter tractability results and kernelizations for STC [Golovach et al., SWAT'18, Grüttemeier and Komusiewicz, WG'18] to the three variants with multiple edge colors or outline the limits of such an extension.
READ FULL TEXT