Orientable burning number of graphs
Résumé
In this paper, we introduce the problem of finding an orientation of a given undirected graph
that maximizes the burning number of the resulting directed graph. We show that the problem
is polynomial-time solvable on Kőnig–Egerváry graphs (and thus on bipartite graphs) and that
an almost optimal solution can be computed in polynomial time for perfect graphs. On the
other hand, we show that the problem is NP-hard in general and W[1]-hard parameterized by
the target burning number. The hardness results are complemented by several fixed-parameter
tractable results parameterized by structural parameters. Our main result in this direction
shows that the problem is fixed-parameter tractable parameterized by cluster vertex deletion
number plus clique number (and thus also by vertex cover number).
Origine | Fichiers produits par l'(les) auteur(s) |
---|
Origine | Fichiers produits par l'(les) auteur(s) |
---|