Source-linked AI summary
Perfect Italian Domination on and Near Split Graphs: Algorithms, Hardness, and Approximation
Anand Babu N B, Ashwin Jacob, Manjusha M S, Renjith P
TL;DR
PID’s complexity on split graphs was open, against a backdrop of hardness on chordal graphs and tractability on several narrower classes. The paper gives a polynomial-time split-graph algorithm and classifies complexity and approximation behavior for nearby extensions.
Problem
PID is NP-complete on chordal graphs but polynomial-time solvable on several narrower classes, and its status on split graphs was an unresolved boundary question.
Source: §1 · p. 2Method
The paper characterizes clique labelings, reduces the remaining split-graph case to weighted partition and minimum-capacity cut, and studies extensions formed by attaching pendant stars.
Source: §1 · p. 2Results
An O(n^4)-time algorithm solves PID on split graphs, while PID is NP-complete at split-deletion distance one and on strict K1,1-split graphs.
Source: §3.1 · p. 7, §4 · p. 11, §5 · p. 12Takeaways & Limitations
The results locate a sharp tractability boundary at split graphs and classify strict K1,r extensions as hard for r = 1, 2 and exactly solvable in linear time for fixed r ≥ 3.
Source: §1 · pp. 2–3
Abstract
from arXiv · showhide
A perfect Italian dominating function assigns a label from $\{0,1,2\}$ to each vertex so that the labels in the neighborhood of every zero-labeled vertex sum to exactly two. Although the associated decision problem (PID) is NP-complete on chordal graphs, the complexity status on split graphs remains open. We give an $O(n^4)$ time algorithm for split graphs on $n$ vertices. We note that this is in contrast to Roman, Italian, and perfect Roman domination, which are NP-complete on split graphs. We further show that this tractability boundary is tight: PID is NP-hard on graphs at deletion distance one from split graphs. We also provide dichotomy results for PID on restricted extensions of split graphs formed by attaching pendant stars, and establish inapproximability results for the same.
1 Introduction
PID’s complexity varies across graph classes, making split graphs a useful place to locate the boundary between tractability and NP-completeness. The paper proves split-graph tractability, hardness at split-deletion distance one, and complexity and approximation results for star extensions.
1 Introduction
- PID is NP-complete on chordal graphs but polynomial-time solvable on several narrower classes, motivating a search for the structural boundary between tractability and hardness.The listed tractable classes include block, series–parallel, distance-hereditary, threshold, and cographs.Source: §1 · p. 2
- Split graphs partition into a clique and an independent set with arbitrary adjacencies between the parts, making them a natural class for refining that boundary.The paper also notes that an upper bound on the perfect Italian domination number is tight for connected split graphs, but that extremal construction does not compute an optimum function.Source: §1 · p. 2
- An O(n^4)-time algorithm computes a minimum-weight PID-function on split graphs by reducing the remaining case to weighted partition and minimum-capacity cut problems.The algorithm first characterizes possible clique labelings.Source: §1 · p. 2
- PID is NP-complete at split-deletion distance one, so parameterization by that distance is para-NP-hard unless P = NP.The result contrasts with polynomial-time solvability on split graphs.Source: §1 · p. 2
- PID is NP-complete on strict K1,1-split graphs, while strict K1,r-split graphs admit a linear-time algorithm for every fixed r ≥ 3; strict r = 2 is known to be hard.Every non-strict K1,r class with fixed r ≥ 1 is NP-complete because it contains the strict K1,1 class.Source: §1 · p. 3
- At split-deletion distance exactly one, no polynomial-time (2 − ε)-approximation exists for fixed 0 < ε < 1 unless P = NP; strict K1,1-split graphs have no PTAS even when |K| ≤ |I|.For strict r ∈ {1, 2} with |K| ≤ c|I| for fixed c, the paper gives constant-factor approximation algorithms.Source: §1 · p. 3
2 Graph Preliminaries
The preliminaries define the graph conventions and the split and K1,r-split classes used in the paper. They also specify the strictness and balance conditions for the star extensions.
2 Graph Preliminaries
- Graphs are finite, simple, and connected unless stated otherwise; neighborhoods and induced subgraphs use the paper’s stated notation.The open neighborhood of a vertex excludes the vertex itself, while its closed neighborhood includes it.Source: §2 · p. 3
- A split graph has a partition into a clique K and an independent set I, with K taken maximal unless stated otherwise.A chordal graph has no induced cycle of length at least four.Source: §2 · p. 3
- A K1,r-split graph has a clique K and disjoint stars outside it, whose centers may neighbor K while each leaf is adjacent only to its center.The non-strict class allows stars with zero through r leaves; the strict class requires every star to have exactly r leaves, and strict K1,0-split graphs are split graphs.Source: §2 · pp. 3–4
- In a strict K1,1-split graph each center has one leaf, and an instance is balanced when |K| ≤ c|I| for fixed c independent of graph size.Here |I| counts star centers, not clique vertices or leaves.Source: §2 · pp. 3–4
3 Perfect Italian Domination in Split Graphs
The section divides clique labelings into five exhaustive cases, handling cases with zero-labeled clique vertices separately from the all-positive case. That remaining case becomes a weighted partition problem reducible to a minimum cut.
3 Perfect Italian Domination in Split Graphs
- Five exhaustive cases classify clique labelings: four contain a zero-labeled clique vertex, while the fifth has every clique vertex positive.The first four cases can be solved in polynomial time.Source: §3 · p. 4
- When every clique label is zero, connectedness and the neighborhood-sum constraints force independent-side labels whose consistency determines feasibility.Vertices of the independent set with degree zero or at least three are impossible in this case.Source: §3 · p. 5
- With one clique vertex labeled 1, all independent vertices receive 1 and each other clique vertex needs one further unit; with a sole 2, its vertex must neighbor all of I.In the sole-2 case, all other vertices can then receive 0.Source: §3 · p. 5
- With two clique vertices labeled 1, an independent vertex can receive 0 exactly when adjacent to both; other independent vertices receive 1.Every other clique vertex must have all its independent neighbors adjacent to both labeled vertices.Source: §3 · p. 5
- When all clique vertices are positive, an independent vertex receives 0 exactly when its clique-neighbor labels sum to 2; otherwise it receives 1, yielding a weighted partition objective.The partition labels K1 by 1 and K2 by 2, and its minimum cost gives the minimum weight in this case.Source: §3 · pp. 5–6
3.1 Minimum-Capacity Cut Formulation
- The weighted partition reduces to a minimum-capacity cut, and the resulting algorithm computes a minimum-weight PID-function on split graphs in O(n^4) time.A minimum cut recovers an optimal partition, which combines with the other clique-labeling cases to establish the algorithm.Source: §3.1 · p. 7
4 Hardness at Split-Deletion Distance One
PID is NP-complete on graphs at split-deletion distance one, establishing hardness immediately beyond split graphs; the reduction encodes Restricted Exact Cover by 3-Sets.
4 Hardness at Split-Deletion Distance One
- PID is NP-complete on graphs G with split-deletion distance one, and parameterization by that distance is para-NP-hard unless P = NP.The reduction is from Restricted Exact Cover by 3-Sets.Source: §4 · pp. 9, 11
- Deleting s leaves a split partition (C, X), while the constructed graph itself has split-deletion distance one.The construction joins s to test and set vertices, and a four-cycle shows the graph is not split.Source: §4 · p. 9
- An exact cover yields a PID-function of weight q + 2 in the reduction graph.The construction sets s and w to one and labels the vertices corresponding to the selected sets; the resulting function has weight q + 2.Source: §4 · p. 9
- Conversely, a PID-function within the reduction's weight bound forces the selected set vertices to form an exact cover.The reverse implication analyzes the possible labels of s; in the surviving case, every element belongs to exactly one positively labeled set.Source: §4 · pp. 9–11
5 Complexity on K1,r-Split Graphs
Attaching pendant stars to independent-side vertices produces distinct complexity regimes: non-strict classes are hard for every fixed r ≥ 1, while strict classes become tractable for r ≥ 3.
5 Complexity on K1,r-Split Graphs
- The section studies split-graph extensions formed by attaching private leaves to independent-side vertices.In the strict K1,r-split setting, each independent-side center has r private leaves; strictness is distinguished from the non-strict classes discussed in the results.Source: §5 · p. 11
- PID is NP-complete on strict K1,1-split graphs and on non-strict K1,r-split graphs for every fixed r ≥ 1.The strict K1,1 result is proved by reduction from Restricted Exact Cover by 3-Sets.Source: §5 · p. 12
- On strict K1,r-split graphs, PID is NP-complete for r = 1, 2, but a minimum PID-function is computable in O(n + m) time for every fixed r ≥ 3.The linear-time algorithm requires no balance assumption.Source: §5 · p. 12
6 Approximation and Inapproximability
The paper establishes approximation lower bounds for graphs near split graphs and pendant-star extensions, alongside guarantees for balanced strict star classes.
6 Approximation and Inapproximability
- No polynomial-time (2 − ε)-approximation exists for minimum PID on graphs with split-deletion distance one, for any fixed 0 < ε < 1, unless P = NP.The same lower bound applies for every fixed distance bound d ≥ 1, ruling out a PTAS but not a 2-approximation.Source: §6 · p. 12
- Minimum PID on strict K1,1-split graphs has no PTAS unless P = NP, even when |K| ≤ |I|.Source: §6 · p. 13
- Strict K1,r-split graphs for fixed r ≥ 3 admit an exact algorithm, without a balance assumption.Source: §6 · p. 13
- For balanced strict graphs with |K| ≤ c|I|, linear-time approximations achieve ratio c + 2 for r = 1 and 1 + c/2 for r = 2.When |K| ≤ |I|, these ratios are three and 3/2, respectively.Source: §6 · p. 13
Declaration of AI Use
The authors disclose using an AI assistant during manuscript preparation and state that they verified the results and take responsibility for the manuscript.
Declaration of AI Use
- An AI assistant was used for language editing, LaTeX formatting, idea formulation, organization, and checking mathematical arguments.The authors state that they verified the results and take full responsibility for the manuscript's integrity.Source: Declaration of AI Use · p. 13
A.1 Proof of Lemma 6
Strict K1,r-split graphs can be recognized and partitioned in linear time, with all defining partitions of a connected instance having the same part sizes. The recognition method handles forced partitions for r ≥ 2 and a small exceptional case for r = 1.
A.1 Proof of Lemma 6
- Recognition and recovery of a defining partition take O(n + m) time, and all defining partitions of a connected strict instance have the same part sizes.The algorithm checks a constant number of candidate partitions.Source: §A.1 · pp. 15–16
- For r ≥ 2, degree-one neighbors force the center set; the resulting candidate partition is verified or rejected.The method takes I from vertices with at least r degree-one neighbors, then forms J and K from the remaining vertices.Source: §A.1 · p. 15
- For r = 1, after the ordinary candidate fails, the only remaining valid form has a two-vertex clique and is tested using a star on C.At most three candidate partitions need verification.Source: §A.1 · p. 15
A.2 Proof of Lemma 7
In a minimum PID-function on a strict K1,1-split graph with at least one center, every clique vertex has label at most one. The proof rules out a clique label of two by constructing a lower-weight function in each possible case.
A.2 Proof of Lemma 7
- Every clique vertex has label at most one in a minimum PID-function when the graph has at least one center.The proof assumes a clique vertex w has label two and derives a lower-weight PID-function in all cases.Source: §A.2 · p. 16
- When a zero clique vertex has a center neighbor, relabeling that vertex, w, and the centers’ leaves preserves the zero-neighbor sums while lowering weight.The affected centers are not adjacent to w and had leaves labeled two.Source: §A.2 · p. 16
- If no zero clique vertex has a center neighbor, every center is adjacent only to w, and a different relabeling again gives a lower-weight PID-function.The construction sets w and a zero clique vertex to one, each center to zero, and each private leaf to one.Source: §A.2 · p. 16
A.3 Proof of Theorem 3
PID is NP-complete on strict K1,1-split graphs via a reduction from Restricted Exact Cover by 3-Sets. The construction has a PID-function within its weight bound exactly when the instance has an exact cover.
A.3 Proof of Theorem 3
- PID is NP-complete on strict K1,1-split graphs by reduction from Restricted Exact Cover by 3-Sets.The reduction uses a strict K1,1-split graph with 15q + 1 vertices and weight bound B = 9q + 1.Source: §A.3 · pp. 16–17
- The reduction makes X together with z a clique and creates set and auxiliary center–leaf pairs with distinct adjacencies to that clique.Set centers encode the triples; the first three auxiliary centers also meet every element vertex.Source: §A.3 · p. 17, Figure 4 · p. 17
- An exact cover yields a PID-function of weight 9q + 1 by labeling z, selected set centers and leaves, and auxiliary leaves as specified.Each element vertex receives one from z and one from its unique selected set.Source: §A.3 · p. 17
- Conversely, any PID-function within the bound forces z to have label one and each element to have exactly one adjacent set center labeled one, yielding an exact cover.The equality conditions in the weight lower bound force the selected set centers to cover every element exactly once.Source: §A.3 · pp. 17–18
- The full illustrative reduction graph displays the exact cover {S2, S4}, with clique edges suppressed in the drawing.Its set centers encode the six sets, and each center has a private leaf.Source: Figure 5 · p. 18
A.4 Proof of Theorem 4
The section establishes a complexity dichotomy for strict star extensions, hardness of approximation in two settings, and linear-time approximation guarantees under a balance condition. For strict K1,r-split graphs, PID is hard for r = 1, 2 but admits a linear-time algorithm for fixed r ≥ 3.
A.4 Proof of Theorem 4
- For strict K1,r-split graphs, PID is NP-complete for r = 1, 2, while a minimum PID-function is computable in O(n + m) time for every fixed r ≥ 3.The algorithm minimizes among four clique-label cases and does not require a balance assumption.Source: §A.4 · pp. 19–20
A.5 Proof of Theorem 5
- No polynomial-time (2−ε)-approximation exists for minimum PID when split-deletion distance is one, unless P = NP.The reduction makes a graph that becomes split after deleting one vertex and separates yes-instance weight q + 2 from no-instance weight at least 2q + 2.Source: §A.5 · pp. 20–21
A.6 Proof of Theorem 6
- Minimum PID on strict K1,1-split graphs has no PTAS unless P = NP, even when |K| ≤ |I|.The reduction is balanced and uses a matching-gap construction.Source: §A.6 · pp. 21–22
- For the strict K1,1-split reduction, the optimum is 1 + m + 6q − 2ν(T), linking the PID weight to the maximum matching size.A matching of size t gives a PID-function of weight 1 + m + 6q − 2t.Source: §A.6 · p. 22
A.7 Proof of Proposition 1
- When |K| ≤ c|I|, linear-time approximations achieve ratio c + 2 for r = 1 and 1 + c/2 for r = 2.The construction labels clique vertices one, centers two, and leaves zero.Source: §A.7 · p. 23