Fioravantes, F, Melissinos, N and Triommatis, T 
ORCID: 0009-0004-9398-2046
(2022)
Complexity of Finding Maximum Locally Irregular Induced Subgraphs.
.
Abstract
If a graph G is such that no two adjacent vertices of G have the same degree, we say that G is locally irregular. In this work we introduce and study the problem of identifying a largest induced subgraph of a given graph G that is locally irregular. Equivalently, given a graph G, find a subset S of V (G) with minimum order, such that by deleting the vertices of S from G results in a locally irregular graph; we denote with I(G) the order of such a set S. We first examine some easy graph families, namely paths, cycles, trees, complete bipartite and complete graphs. However, we show that the decision version of the introduced problem is NP-Complete, even for restricted families of graphs, such as subcubic planar bipartite, or cubic bipartite graphs. We then show that we can not even approximate an optimal solution within a ratio of O(n1-1k ), where k ≥ 1 and n is the order the graph, unless P=NP, even when the input graph is bipartite. Then, looking for more positive results, we turn our attention towards computing I(G) through the lens of parameterised complexity. In particular, we provide two algorithms that compute I(G), each one considering different parameters. The first one considers the size of the solution k and the maximum degree Δ of G with running time (2Δ)knO(1), while the second one considers the treewidth tw and Δ of G, and has running time Δ2twnO(1). Therefore, we show that the problem is FPT by both k and tw if the graph has bounded maximum degree Δ. Since these algorithms are not FPT for graphs with unbounded maximum degree (unless we consider Δ + k or Δ + tw as the parameter), it is natural to wonder if there exists an algorithm that does not include additional parameters (other than k or tw) in its dependency. We answer negatively, to this question, by showing that our algorithms are essentially optimal. In particular, we prove that there is no algorithm that computes I(G) with dependence f(k)no(k) or f(tw)no(tw), unless the ETH fails.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | Source info: TCS-D-23-00092 |
| Uncontrolled Keywords: | Locally irregular, largest induced subgraph, FPT, treewidth, W-hardness, approximability. |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 08 Sep 2022 09:28 |
| Last Modified: | 15 Nov 2023 17:21 |
| DOI: | 10.4230/LIPIcs.SWAT.2022.24 |
| Open Access URL: | https://drops.dagstuhl.de/opus/volltexte/2022/1618... |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3163865 |
Dimensions
Dimensions
