On the Kernel and Related Problems in Interval Digraphs

Authors Mathew C. Francis, Pavol Hell, Dalu Jacob



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.17.pdf
  • Filesize: 0.68 MB
  • 17 pages

Document Identifiers

Author Details

Mathew C. Francis
  • Indian Statistical Institute, Chennai Centre, India
Pavol Hell
  • School of Computing Science, Simon Fraser University, Burnaby, Canada
Dalu Jacob
  • Indian Statistical Institute, Chennai Centre, India

Cite AsGet BibTex

Mathew C. Francis, Pavol Hell, and Dalu Jacob. On the Kernel and Related Problems in Interval Digraphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.17

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 in-neighbour (resp. out-neighbour) 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 NP-complete. 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 NP-hard 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 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 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 NP-complete even for planar bipartite graphs, is linear-time solvable on interval bigraphs, which is a class of bipartite (undirected) graphs closely related to interval digraphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Interval digraphs
  • kernel
  • absorbing set
  • dominating set
  • independent set
  • algorithms
  • approximation hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jochen Alber, Hans L Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 33(4):461-493, 2002. Google Scholar
  2. Kenneth P Bogart and Ann N Trenk. Bounded bitolerance digraphs. Discrete Mathematics, 215(1-3):13-20, 2000. Google Scholar
  3. Miroslav Chlebík and Janka Chlebíková. The complexity of combinatorial optimization problems on d-dimensional boxes. SIAM Journal on Discrete Mathematics, 21(1):158-169, 2007. Google Scholar
  4. Vašek Chvátal. On the computational complexity of finding a kernel. Report CRM-300, Centre de Recherches Mathématiques, Université de Montréal, 592, 1973. Google Scholar
  5. Sandip Das, Mathew Francis, Pavol Hell, and Jing Huang. Recognition and characterization of chronological interval digraphs. the electronic journal of combinatorics, pages P5-P5, 2013. Google Scholar
  6. Sandip Das, M Sen, AB Roy, and Douglas B West. Interval digraphs: An analogue of interval graphs. Journal of Graph Theory, 13(2):189-202, 1989. Google Scholar
  7. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Incompressibility through colors and ids. In International Colloquium on Automata, Languages, and Programming, pages 378-389. Springer, 2009. Google Scholar
  8. Pierre Duchet. A sufficient condition for a digraph to be kernel-perfect. Journal of graph theory, 11(1):81-85, 1987. Google Scholar
  9. Tomás Feder, Pavol Hell, Jing Huang, and Arash Rafiey. Adjusted interval digraphs. Electronic Notes in Discrete Mathematics, 32:83-91, 2009. Google Scholar
  10. Aviezri S Fraenkel. Planar kernel and grundy with d ≤ 3, d_out ≤ 2, d_in ≤ 2 are np-complete. Discrete Applied Mathematics, 3(4):257-262, 1981. Google Scholar
  11. Mathew C Francis, Pavol Hell, and Dalu Jacob. On the kernel and related problems in interval digraphs. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.08278.
  12. Michael R Garey and David S Johnson. Computers and intractability. A Guide to the, 1979. Google Scholar
  13. TeresaW Haynes. Domination in graphs: volume 2: advanced topics. Routledge, 2017. Google Scholar
  14. Ryan B. Hayward, Jeremy Spinrad, and R. Sritharan. Weakly chordal graph algorithms via handles. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00, pages 42-49, USA, 2000. Society for Industrial and Applied Mathematics. Google Scholar
  15. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Classes of intersection digraphs with good algorithmic properties. arXiv preprint, 2021. URL: http://arxiv.org/abs/2105.01413.
  16. Ekkehard Köhler and Lalla Mouatadid. A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs. Information Processing Letters, 116(6):391-395, 2016. Google Scholar
  17. Dieter Kratsch and Lorna Stewart. Domination on cocomparability graphs. SIAM Journal on Discrete Mathematics, 6(3):400-417, 1993. Google Scholar
  18. Ching-Hao Liu, Sheung-Hung Poon, and Jin-Yong Lin. Independent dominating set problem revisited. Theoretical Computer Science, 562:1-22, 2015. Google Scholar
  19. Ross M McConnell and Jeremy P Spinrad. Modular decomposition and transitive orientation. Discrete Mathematics, 201(1-3):189-241, 1999. Google Scholar
  20. Nimrod Megiddo and Uzi Vishkin. On finding a minimum dominating set in a tournament. Theoretical Computer Science, 61(2-3):307-316, 1988. Google Scholar
  21. Oskar Morgenstern and John Von Neumann. Theory of games and economic behavior. Princeton university press, 1953. Google Scholar
  22. Haiko Müller. Recognizing interval digraphs and interval bigraphs in polynomial time. Discrete Applied Mathematics, 78(1-3):189-205, 1997. Google Scholar
  23. Christos H Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of computer and system sciences, 43(3):425-440, 1991. Google Scholar
  24. Adèle Pass-Lanneau, Ayumi Igarashi, and Frédéric Meunier. Perfect graphs with polynomially computable kernels. Discrete Applied Mathematics, 272:69-74, 2020. Google Scholar
  25. Erich Prisner. A characterization of interval catch digraphs. Discrete mathematics, 73(3):285-289, 1989. Google Scholar
  26. Erich Prisner. Algorithms for interval catch digraphs. Discrete Applied Mathematics, 51(1-2):147-157, 1994. Google Scholar
  27. K Brooks Reid, Alice A McRae, Sandra Mitchell Hedetniemi, and Stephen T Hedetniemi. Domination and irredundance in tournaments. Australasian journal of combinatorics, 29:157-172, 2004. Google Scholar
  28. Moses Richardson. Solutions of irreflexive relations. Annals of Mathematics, pages 573-590, 1953. Google Scholar
  29. Asahi Takaoka. A recognition algorithm for adjusted interval digraphs. Discrete Applied Mathematics, 294:253-256, 2021. Google Scholar
  30. Karsten Weihe. Covering trains by stations or the power of data reduction. Proceedings of Algorithms and Experiments, ALEX, pages 1-8, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail