Complexity analysis of P3P3-convexity problems on bounded-degree and planar graphs

This paper studies new complexity aspects of P3P3-convexity restricted to planar graphs with bounded maximum degree. More specifically, we are interested in identifying either a minimum P3P3-geodetic set or a minimum P3P3-hull set of such graphs, from which the whole vertex set of G is obtained either after one or sufficiently many iterations, respectively. Each iteration adds to a set S   all vertices of V(G)∖SV(G)∖S with at least two neighbors in S  . In this paper it is shown that: a minimum P3P3-hull set of a graph G   can be found in polynomial time when δ(G)≥n(G)c (for some constant c  ); deciding if there is a P3P3-hull set of size at most k   in a given graph remains NP-complete even for planar graphs with maximum degree four; and, surprisingly as well as rather counterintuitively, it is NP-complete to decide if there is a P3P3-hull set of size at most k   in a graph with maximum degree three, though one can determine a minimum P3P3-hull set in polynomial time not only for cubic graphs but also for graphs with minimum feedback vertex set of bounded size and no vertices of degree two. Concerning P3P3-geodetic sets, the problem of deciding if there is a P3P3-geodetic set of size at most k   in a planar graph with maximum degree three is proved to be NP-complete. Finally, from a parameterized point of view, we observe that finding a P3P3-geodetic set of size at most k, where k is the parameter, is W[2]-hard; however, when considering the maximum degree as an additional parameter, this problem becomes fixed-parameter tractable.