Complexity of Finding Maximum Locally Irregular Induced Subgraphs

A graph is said to be locally irregular if it contains no adjacent vertices having the same degree. In this work we introduce and study the problem of finding a largest locally irregular induced subgraph of a given graph \(G\). Equivalently, given a graph \(G\), find a subset \(S\) of \(V(G)\) with minimum order, such that deleting the vertices of \(S\) from \(G\) results in a locally irregular graph; we denote with \({\rm I}(G)\) the order of such a set \(S\). We first examine some simple graph families. We then show that the decision version of the introduced problem is \(\mathsf{NP}\)-complete, even for restricted families of graphs. Moreover, we cannot even approximate an optimal solution within a ratio of \(\mathcal{O}(n^{1-\frac{1}{k}})\), for every \(k\geq 1\), where \(n\) is the order the graph, unless \(\mathsf{P}=\mathsf{NP}\), even when the input graph is bipartite.

For positive results, we provide two \(\mathsf{FPT}\) algorithms for computing \({\rm I}(G)\), the first one considering, as a parameter, the size of the solution \(k\) and the maximum degree \(\Delta\) of \(G\), and the second one considering the treewidth \(tw\) and \(\Delta\) of \(G\), with running times \((2\Delta)^kn^{\mathcal{O}(1)}\) and \(\Delta^{4tw}n^{\mathcal{O}(1)}\) respectively. We then prove that there is no algorithm that computes \({\rm I}(G)\) with dependence \(f(k)n^{o(k)}\) or \(f(tw)n^{o(tw)}\), unless the ETH fails, showing that our algorithms are essentially optimal.

Recording