On the kernel and related problems in interval digraphs

DOI10.1007/S00453-022-01010-1MaRDI QIDQ6103517zbMATH OpenOpenAlexFDO

Authors Mathew C. Francis, Pavol Hell, Dalu Jacob

Publication date 5 June 2023

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.08278, https://eprints.iisc.ac.in/75333/1/alg_2022.pdf

zbMATH Keywords

absorbing setdominating setindependent setinterval digraphskernelreflexive interval digraphs

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Abstract: Given a digraph $G$, a set $XsubseteqV(G)$ is said to be absorbing set (resp. dominating set) if every vertex in the graph is either in $X$ or is an in-neighbour (resp. out-neighbour) of a vertex in $X$. A set $SsubseteqV(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$. 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)inE(G)$ if and only if $S_{u}cap{T}_{v}eqemptyset$. 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 show that all the problems mentioned above are efficiently solvable, in most of the cases even linear-time solvable, in the class of reflexive interval digraphs, but are APX-hard on even the very restricted class of interval digraphs called point-point 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 subclasses of reflexive interval digraphs.

Recommendations

• On the existence of (k,\(\ell)\)-kernels in digraphs
• A note on kernels and solutions in digraphs
• A new generalization of kernels in digraphs
• scientific article; zbMATH DE number 1275896
• Kernels in a special class of digraphs
• On the existence of \(k\)-kernels in digraphs and in weighted digraphs
• k-Kernels and some operations in digraphs
• On kernel-perfect critical digraphs
• On kernels in i-triangulated graphs
• On the kernel of integral circulant graphs

Cites work

• A characterization of interval catch digraphs
• A digraph represented by a family of boxes or spheres
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• A recognition algorithm for adjusted interval digraphs
• A sufficient condition for a digraph to be kernel-perfect
• Algorithms for interval catch digraphs
• Bounded bitolerance digraphs
• College Admissions and the Stability of Marriage
• Dominating sets in \(k\)-majority tournaments.
• Domination in tournaments
• Domination on Cocomparability Graphs
• Extension Theorems for Solutions of Irreflexive Relations
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2104726 (Why is no real title available?)
• scientific article; zbMATH DE number 1445284 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• scientific article; zbMATH DE number 3084669 (Why is no real title available?)
• Incompressibility through Colors and IDs
• Independent dominating set problem revisited
• Interval digraphs: An analogue of interval graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Kernels in perfect line-graphs
• Kernels in random graphs
• Modular decomposition and transitive orientation
• On finding a minimum dominating set in a tournament
• On kernels and semikernels of digraphs
• On kernels in i-triangulated graphs
• On kernels in perfect graphs
• On weakly ordered systems
• Optimization, approximation, and complexity classes
• Perfect graphs are kernel solvable
• Perfect graphs with polynomially computable kernels
• Perfect graphs, kernels, and cores of cooperative games
• Planar kernel and Grundy with d 3, dout 2, din 2 are NP- complete
• Polynomial algorithms for kernels in comparability, permutation and P₄-free graphs
• Recent problems and results about kernels in directed graphs
• Recognition and characterization of chronological interval digraphs
• Recognizing interval bigraphs by forbidden patterns
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Solutions of irreflexive relations
• Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes

Cited in

(2)

• A dichotomy for the kernel by H‐walks problem in digraphs
• Classes of intersection digraphs with good algorithmic properties

This page was built for publication: On the kernel and related problems in interval digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103517)