We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have ...(discrete) time labels. Since the corresponding Temporal(s,z)-Separation problem is NP-complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph—there we observe polynomial-time solvability in the case of bounded treewidth—as well as restrictions concerning the “temporal evolution” along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases.
A perfect matching cut is a perfect matching that is also a cutset, or equivalently, a perfect matching containing an even number of edges on every cycle. The corresponding algorithmic problem, ...Perfect Matching Cut, is known to be NP-complete in subcubic bipartite graphs Le & Telle, TCS '22, but its complexity was open in planar graphs and cubic graphs. We settle both questions simultaneously by showing that Perfect Matching Cut is NP-complete in 3-connected cubic bipartite planar graphs or Barnette graphs. Prior to our work, among problems whose input is solely an undirected graph, only Distance-2 4-Coloring was known to be NP-complete in Barnette graphs. Notably, Hamiltonian Cycle would only join this private club if Barnette's conjecture were refuted.
Let G=(V,E) be a graph where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V, we say AdominatesB if every vertex of B is adjacent to at least one vertex of ...A. A vertex partition π={V1,V2,…,Vk} of G is called a transitive partition of size k if Vi dominates Vj for all 1≤i<j≤k. In this article, we study a variation of transitive partition, namely 2-transitive partition. For two disjoint subsets A and B of V, we say A 2-dominatesB if every vertex of B is adjacent to at least two vertices of A. A vertex partition π={V1,V2,…,Vk} of G is called a 2-transitive partition of size k if Vi2-dominates Vj for all 1≤i<j≤k. The Maximum 2-Transitivity Problem is to find a 2-transitive partition of a given graph with the maximum number of parts. We show that the decision version of this problem is NP-complete for chordal and bipartite graphs. On the positive side, we design three linear-time algorithms for solving Maximum 2-Transitivity Problem in trees, split, and bipartite chain graphs.
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 W2-hard; however, when considering the maximum degree as an additional parameter, this problem becomes fixed-parameter tractable.
Correspondence homomorphisms are a common generalization of homomorphisms and of correspondence colourings. For a fixed reflexive target graph H, the problem is to decide whether an input graph G, ...with each edge labeled by a pair of permutations of V(H), admits a homomorphism to H ‘corresponding’ to the labels. We classify the complexity of this problem as a function of H. It turns out that there is dichotomy—each of the problems is polynomial or NP-complete. While most graphs H yield NP-complete problems, there is an interesting polynomial case when the problem can be solved by Gaussian elimination. We also classify the complexity of the analogous correspondence list homomorphism problems.
Summary
Artificial intelligence‐based (AI‐based) network slicing bandwidth allocation enables the 5G/6G service providers to create multiple virtual networks atop a shared physical infrastructure ...while fulfilling varying end‐user demands. Some researchers argue that AI‐enable network may run the danger of having private information compromised. We still need a backup rule‐based methodology to allocate bandwidth resource to each slice, if the AI‐based method suddenly encounters security issues. To design such a rule‐based methodology, this study attempts to answer two questions: (1) Is the network slicing bandwidth allocation problem the nondeterministic polynomial‐time completeness (NP‐completeness)? (2) Is there a heuristic methodology without any training process, which has equivalent performance compared to the AI‐based methodology? This study first proves the classical network slicing bandwidth allocation problems is NP‐completeness. This shows that the designed heuristic method is inescapably suboptimal to the network slicing bandwidth allocation problem. Secondly, this study proposes the Adaptive Hungarian Algorithm (AHA), which outperforms previous AI‐empowered method and does not need any training process. The experiments demonstrate that AHA reached 93%–97% of the maximal system throughput by brute‐and‐force algorithm, compared to other methodologies only having at most 93% of the maximal system throughput. This also indicates that AHA is capable to solve the network slicing bandwidth allocation problem, if the telecommunication operators do not have sufficient sample complexity to train an AI model.
This study proves the network slicing bandwidth allocation problem is NP‐completeness. A new heuristic algorithm, Adaptive Hungarian Algorithm, is also designed and reaches 93%–97% of the optimal system throughput, which can be as a substitute to the AI‐based methodology.
A conjecture of Berge predicts that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. If the graph in question has no 3-edge-colouring, then at least four ...perfect matchings are necessary. It was proved by Esperet and Mazzuoccolo (2014) 3 that it is NP-complete to decide whether four perfect matchings are enough to cover the edges of a bridgeless cubic graph. A disadvantage of the proof (noted by the authors) is that the constructed graphs have 2-cuts. In this paper we show that small cuts can be altogether avoided and that the problem remains NP-complete even for nontrivial snarks – that is, cyclically 4-edge-connected cubic graphs with no 3-edge-colouring. As a by-product, we provide a rich family of nontrivial snarks that cannot be covered with four perfect matchings. The methods rely on the theory of tetrahedral flows developed in Máčajová and Škoviera (2021) 9.
This paper studies the problem of, given the structure of a linear-time invariant system and a set of possible inputs, finding the smallest subset of input vectors that ensures system’s structural ...controllability. We refer to this problem as the minimum constrained input selection (minCIS) problem, since the selection has to be performed on an initial given set of possible inputs. We prove that the minCIS problem is NP-hard, which addresses a recent open question of whether there exist polynomial algorithms (in the size of the system plant matrices) that solve the minCIS problem. To this end, we show that the associated decision problem, to be referred to as the CIS, of determining whether a subset (of a given collection of inputs) with a prescribed cardinality exists that ensures structural controllability, is NP-complete. Further, we explore in detail practically important subclasses of the minCIS obtained by introducing more specific assumptions either on the system dynamics or the input set instances for which systematic solution methods are provided by constructing explicit reductions to well known computational problems. The analytical findings are illustrated through examples in multi-agent leader–follower type control problems.
PDF
