Name
Abstract | ||
|---|---|---|
This paper studies new complexity aspects of P3-convexity restricted to planar graphs with bounded maximum degree. More specifically, we are interested in identifying either a minimum P3-geodetic set or a minimum P3-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)∖S with at least two neighbors in S. In this paper it is shown that: a minimum P3-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 P3-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 P3-hull set of size at most k in a graph with maximum degree three, though one can determine a minimum P3-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 P3-geodetic sets, the problem of deciding if there is a P3-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 P3-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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.tcs.2015.10.003 | Theoretical Computer Science |
Keywords | Field | DocType |
FPT,NP-completeness,Parametrization,W[2]-hard | Discrete mathematics,Dominating set,Combinatorics,Chordal graph,Independent set,Degree (graph theory),Pathwidth,1-planar graph,Mathematics,Feedback vertex set,Maximal independent set | Journal |
Volume | ISSN | Citations |
607 | 0304-3975 | 1 |
PageRank | References | Authors |
0.36 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lucia Draque Penso | 1 | 196 | 20.46 |
| Fábio Protti | 2 | 357 | 46.14 |
| Dieter Rautenbach | 3 | 946 | 138.87 |
| Uéverton dos Santos Souza | 4 | 1 | 0.36 |