In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\mathsf {NP}}$$NP -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is $${\mathsf {NP}}$$NP -complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$c > 1 , Matching Cut is $${\mathsf {NP}}$$NP -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\epsilon >0$$ϵ > 0 , Matching Cut remains $${\mathsf {NP}}$$NP -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree $$\delta >n^{1-\epsilon }$$δ > n 1 - ϵ . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree $$\delta \ge 3$$δ ≥ 3 in $$O^*(\lambda ^n)$$O ∗ ( λ n ) time, where $$\lambda$$λ is the positive root of the polynomial $$x^{\delta +1}-x^{\delta }-1$$x δ + 1 - x δ - 1 . Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$O ∗ ( 1 . 0099 n ) on graphs with minimum degree $$\delta \ge 469$$δ ≥ 469 . Complementing our hardness results, we show that, for any two fixed constants $$1< c <4$$1 < c < 4 and $$c^{\prime }\ge 0$$c ′ ≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree $$\delta \ge \frac{1}{c}n-c^{\prime }$$δ ≥ 1 c n - c ′ .

In order to solve the problem of large model computing power consumption, this paper proposes a novel model compression algorithm. Firstly, this paper proposes an interpretable weight allocation method for the loss between a student network (a network model with poor performance), a teacher network (a network model with better performance) and real label. Then, different from the previous simple pruning and fine-tuning, this paper performs knowledge distillation on the pruned model, and quantifies the residual weights of the distilled model. The above operations can further reduce the model size and calculation cost while maintaining the model accuracy. The experimental results show that the weight allocation method proposed in this paper can allocate a relatively appropriate weight to the teacher network and real tags. On the cifar-10 dataset, the pruning method combining knowledge distillation and quantization can reduce the memory size of resnet32 network model from 3726 KB to 1842 KB, and the accuracy can be kept at 93.28%, higher than the original model. Compared with similar pruning algorithms, the model accuracy and operation speed are greatly improved.

This Special Issue is focused on breakthrough developments in the field of Internet of Multimedia Things (IoMT), particularly on smart and future applications of IoMT using big data analytics