Search

The Min Anonymous-Edge-Rotation problem asks for an input graph G and a positive integer k to find a minimum number of edge rotations that transform G into a graph such that for each vertex there are at least k − 1 other vertices of the same degree (a k-degree-anonymous graph). In this paper, we prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k = n / q , where n is the order of a graph and q any positive integer, q ≥ 3 . We argue that under some constrains on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Furthermore, we show that the problem is solvable in polynomial time for any graph when k = n and for trees when k = θ ( n ) . Additionally, we establish sufficient conditions for an input graph and k such that a solution for Min Anonymous-Edge-Rotation exists.

A proportionally dense subgraph (PDS) is an induced subgraph of a graph such that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the rest of the graph. In this paper, we study a partition of a graph into two proportionally dense subgraphs, namely a 2-PDS partition, with and without additional constraint of connectivity of the subgraphs. We present two infinite classes of graphs: one with graphs without a 2-PDS partition, and another with graphs that only admit a disconnected 2-PDS partition. These results answer some questions proposed by Bazgan et al. [Algorithmica 80(6)(2018), 1890–1908].

A graph is k-degree-anonymous if for each vertex there are at least \(k-1 \) other vertices of the same degree in the graph. Min Anonymous-Edge-Rotation asks for a given graph G and a positive integer k to find a minimum number of edge rotations that transform G into a k-degree-anonymous graph. In this paper, we establish sufficient conditions for an input graph and k ensuring that a solution for the problem exists. We also prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for \(k=n/3\), where n is the order of a graph. On the positive side, we argue that under some constraints on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Moreover, we show that the problem is solvable in polynomial time for any graph when \(k=n\) and for trees when \(k=\theta (n)\).

We consider the complexity of the firefighter problem where a budget of b≥1 firefighters are available at each time step. This problem is known to be NP-complete even on trees of degree at most three and b=1 [S. Finbow, A. King, G. MacGillivray, and R. Rizzi. The firefighter problem for graphs of maximum degree three. Discrete Mathematics, 307(16):2094-2105, 2007] and on trees of bounded degree (b+3 for any fixed b≥2 [C. Bazgan, M. Chopin, and B. Ries. The firefighter problem with more than one firefighter on trees. Discrete Applied Mathematics, 161(7-8):899-908, 2013]. In this paper we provide further insight into the complexity landscape of the problem by showing a complexity dichotomy result with respect to the parameters pathwidth and maximum degree of the input graph. More precisely, first, we prove that the problem is NP-complete even on trees of pathwidth at most three for any b≥1. Then we show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter "pathwidth" and "maximum degree" of the input graph. Finally, we show that the problem remains NP-complete on very dense graphs, namely co-bipartite graphs, but is fixed-parameter tractable with respect to the parameter "cluster vertex deletion".