(Strong) conflict-free connectivity: Algorithm and complexity

Let G be an(a) edge(vertex)-colored graph. A path P of G is called a conflict-free path if there is a color that is used on exactly one of the edges(vertices) of P. The graph G is called conflict-free (vertex-)connected if any two distinct vertices of G are connected by a conflict-free path, whereas the graph G is called strongly conflict-free connected if any two distinct vertices u, v of G are connected by a conflict-free path of length of a shortest path between u and v in G. For a connected graph G, the (strong)conflict-free connection number of G, denoted by (scfc(G)) cf c(G), is defined as the smallest number of colors that are required to make G (strongly) conflict-free connected. In this paper, we first investigate the question: Given a connected graph G and a coloring c : E(or V) ->{1, 2, ..., k} (k >= 1) of G, determine whether or not G is, respectively, conflict-free connected, conflict-free vertexconnected, strongly conflict-free connected under the coloring c. We solve this question by providing polynomial-time algorithms. We then show that the problem of deciding whether scfc(G) <= k (k >= 2) for a given graph G is NP-complete. Moreover, we prove that it is NP-complete to decide whether there is a k-edge-coloring (k >= 2) of G such that all pairs (u, v) is an element of P (P subset of V x V) are strongly conflict-free connected. (C) 2019 Elsevier B.V. All rights reserved.