Feder, Tomás; Hell, Pavol; Huang, Jing; Rafiey, Arash Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. (English) Zbl 1236.05092 Discrete Appl. Math. 160, No. 6, 697-707 (2012). Summary: Interval graphs admit linear-time recognition algorithms and have several elegant forbidden structure characterizations. Interval digraphs can also be recognized in polynomial time, and they admit a characterization in terms of incidence matrices. Nevertheless, they do not have a known forbidden structure characterization or low-degree polynomial-time recognition algorithm. We introduce a new class of ‘adjusted interval digraphs’. By contrast, for these digraphs we exhibit a natural forbidden structure characterization, in terms of a novel structure which we call an ‘invertible pair’. Our characterization also yields a low-degree polynomial-time recognition algorithm of adjusted interval digraphs. It turns out that invertible pairs are also useful for undirected interval graphs, and our result yields a new forbidden structure characterization of interval graphs. In fact, it can be shown to be a natural link proving the equivalence of some known characterizations of interval graphs – the theorems of Lekkerkerker and Boland, and of Fulkerson and Gross. In addition, adjusted interval digraphs naturally arise in the context of list homomorphism problems. If \(H\) is a reflexive undirected graph, the list homomorphism problem \(LHOM(H)\) is polynomial if \(H\) is an interval graph, and NP-complete otherwise. If \(H\) is a reflexive digraph, \(LHOM(H)\) is polynomial if \(H\) is an adjusted interval graph, and we conjecture that it is also NP-complete otherwise. We show that our results imply the conjecture in two important cases. Cited in 17 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C85 Graph algorithms (graph-theoretic aspects) Keywords:interval graphs; interval digraphs; adjusted interval digraphs; forbidden structure characterizations; polynomial algorithms; list homomorphism problems; dichotomy PDFBibTeX XMLCite \textit{T. Feder} et al., Discrete Appl. Math. 160, No. 6, 697--707 (2012; Zbl 1236.05092) Full Text: DOI References: [1] Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci., 13, 335-379 (1976) · Zbl 0367.68034 [2] A.A. Bulatov, Tractable conservative constraint satisfaction problems, ACM Trans. Comput. Logic 12 (4) (tentative) (in press).; A.A. Bulatov, Tractable conservative constraint satisfaction problems, ACM Trans. Comput. Logic 12 (4) (tentative) (in press). · Zbl 1351.68113 [3] C. Carvalho, Personal communication.; C. Carvalho, Personal communication. [4] Corneil, D. G.; Olariu, S.; Stewart, L., The LBFS structure and recognition of interval graphs, SIAM J. Discrete Math., 23, 1905-1953 (2009) · Zbl 1207.05131 [5] S. Das, M. Francis, P. Hell, J. Huang, Recognition and characterization of chronological interval digraphs, manuscript 2011.; S. Das, M. Francis, P. Hell, J. Huang, Recognition and characterization of chronological interval digraphs, manuscript 2011. · Zbl 1295.05161 [6] Feder, T.; Hell, P., List homomorphisms to reflexive graphs, J. Combin. Theory B, 72, 236-250 (1998) · Zbl 0904.05078 [7] T. Feder, P. Hell, The retraction and subretraction problems for reflexive digraphs, manuscript 2008.; T. Feder, P. Hell, The retraction and subretraction problems for reflexive digraphs, manuscript 2008. [8] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 487-505 (1999) · Zbl 0985.05048 [9] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 61-80 (2003) · Zbl 1057.05033 [10] Feder, T.; Hell, P.; Huang, J.; Rafiey, A., Adjusted interval digraphs, Electron. Notes Discrete Math., 32, 83-91 (2009) · Zbl 1267.05257 [11] Feder, T.; Hell, P.; Tucker-Nally, K., Digraph matrix partitions and trigraph homomorphisms, Discrete Appl. Math., 154, 2458-2469 (2006) · Zbl 1106.05060 [12] Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001 [13] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 [14] Gutjahr, W.; Welzl, E.; Woeginger, G., Polynomial graph-colorings, Discrete Appl. Math., 35, 29-45 (1992) · Zbl 0761.05040 [15] Habib, M.; McConnell, R.; Paul, C.; Viennot, L., Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoret. Comput. Sci., 234, 59-84 (2000) · Zbl 0945.68189 [16] Halin, R., Some remarks on interval graphs, Combinatorica, 2, 297-304 (1982) · Zbl 0513.05051 [17] Hell, P., From graph colouring to constraint satisfaction: there and back again, (Topics in Discrete Mathematics. Topics in Discrete Mathematics, Algorithms and Combinatorics Series, vol. 26 (2006), Springer Verlag), 407-432 · Zbl 1116.05028 [18] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139 [19] P. Hell, A. Rafiey, List homomorphisms to irreflexive digraphs, manuscript 2007.; P. Hell, A. Rafiey, List homomorphisms to irreflexive digraphs, manuscript 2007. [20] P. Hell, A. Rafiey, The dichotomy of list homomorphisms for digraphs, in: ACM-SIAM SODA 2011, pp. 1703-1713.; P. Hell, A. Rafiey, The dichotomy of list homomorphisms for digraphs, in: ACM-SIAM SODA 2011, pp. 1703-1713. · Zbl 1376.68067 [21] Larose, B., Taylor operations on finite reflexive structures, Int. J. Math. Comput. Sci., 1, 1-26 (2006) · Zbl 1100.08003 [22] Lekkerkerker, C. G.; Boland, J. C., Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51, 45-64 (1962) · Zbl 0105.17501 [23] Mueller, H., Recognizing interval digraphs and interval bigraphs in polynomial time, Discrete Appl. Math., 78, 189-205 (1997) · Zbl 0890.68103 [24] Prisner, E., A characterization of interval catch digraphs, Discrete Math., 73, 285-289 (1989) · Zbl 0669.05038 [25] Sen, M.; Das, S.; Roy, A. B.; West, D. B., Interval digraphs: an analogue of interval graphs, J. Graph Theory, 13, 581-592 (1989) · Zbl 0671.05039 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.