Francis, Mathew C. ;
Hell, Pavol ;
Jacob, Dalu
On the Kernel and Related Problems in Interval Digraphs
Abstract
Given a digraph G, a set X ⊆ V(G) is said to be an absorbing set (resp. dominating set) if every vertex in the graph is either in X or is an inneighbour (resp. outneighbour) of a vertex in X. A set S ⊆ V(G) is said to be an independent set if no two vertices in S are adjacent in G. A kernel (resp. solution) of G is an independent and absorbing (resp. dominating) set in G. The problem of deciding if there is a kernel (or solution) in an input digraph is known to be NPcomplete. Similarly, the problems of computing a minimum cardinality kernel, absorbing set (or dominating set) and the problems of computing a maximum cardinality kernel, independent set are all known to be NPhard for general digraphs. We explore the algorithmic complexity of these problems in the well known class of interval digraphs. A digraph G is an interval digraph if a pair of intervals (S_u,T_u) can be assigned to each vertex u of G such that (u,v) ∈ E(G) if and only if S_u ∩ T_v ≠ ∅. Many different subclasses of interval digraphs have been defined and studied in the literature by restricting the kinds of pairs of intervals that can be assigned to the vertices. We observe that several of these classes, like interval catch digraphs, interval nest digraphs, adjusted interval digraphs and chronological interval digraphs, are subclasses of the more general class of reflexive interval digraphs  which arise when we require that the two intervals assigned to a vertex have to intersect. We see as our main contribution the identification of the class of reflexive interval digraphs as an important class of digraphs. We show that all the problems mentioned above are efficiently solvable, in most of the cases even lineartime solvable, in the class of reflexive interval digraphs, but are APXhard on even the very restricted class of interval digraphs called pointpoint digraphs, where the two intervals assigned to each vertex are required to be degenerate, i.e. they consist of a single point each. The results we obtain improve and generalize several existing algorithms and structural results for reflexive interval digraphs. We also obtain some new results for undirected graphs along the way: (a) We get an O(n(n+m)) time algorithm for computing a minimum cardinality (undirected) independent dominating set in cocomparability graphs, which slightly improves the existing O(n³) time algorithm for the same problem by Kratsch and Stewart; and (b) We show that the Red Blue Dominating Set problem, which is NPcomplete even for planar bipartite graphs, is lineartime solvable on interval bigraphs, which is a class of bipartite (undirected) graphs closely related to interval digraphs.
BibTeX  Entry
@InProceedings{francis_et_al:LIPIcs.ISAAC.2021.17,
author = {Francis, Mathew C. and Hell, Pavol and Jacob, Dalu},
title = {{On the Kernel and Related Problems in Interval Digraphs}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {17:117:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15450},
URN = {urn:nbn:de:0030drops154505},
doi = {10.4230/LIPIcs.ISAAC.2021.17},
annote = {Keywords: Interval digraphs, kernel, absorbing set, dominating set, independent set, algorithms, approximation hardness}
}
30.11.2021
Keywords: 

Interval digraphs, kernel, absorbing set, dominating set, independent set, algorithms, approximation hardness 
Seminar: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Issue date: 

2021 
Date of publication: 

30.11.2021 