×

Adjusted interval digraphs. (English) Zbl 1267.05257

Koster, Arie (ed.) et al., DIMAP workshop on algorithmic graph theory. Extended abstracts from the workshop held at the University of Warwick, Coventry, UK, March 23–25, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 32, 83-91 (2009).
Summary: Interval digraphs were introduced by West et al. They can be recognized in polynomial time and admit a characterization in terms of incidence matrices. Nevertheless, they do not have a forbidden structure characterization nor a low-degree polynomial recognition algorithm.
We introduce a new class of ‘adjusted interval digraphs,’ obtained by a slight change in the definition. We show that, by contrast, these digraphs have a natural forbidden structure characterization, parallel to a characterization for undirected graphs, and admit a simple recognition algorithm. We relate adjusted interval digraphs to a list homomorphism problem. Each digraph \(H\) defines a corresponding list homomorphism problem \(\mathsf{L-HOM}(H)\). We observe that if \(H\) is an adjusted interval digraph, then the problem \(\mathsf{L-HOM}(H)\) is polynomial time solvable, and conjecture that for all other reflexive digraphs \(H\) the problem \(\mathsf{L-HOM}(H)\) is NP-complete. We present some preliminary evidence for the conjecture, including a proof for the special case of semi-complete digraphs.
For the entire collection see [Zbl 1239.05006].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bulatov, A.A. Tractable conservative constraint satisfaction problems; Bulatov, A.A. Tractable conservative constraint satisfaction problems · Zbl 1351.68113
[2] Carvalho, C.A. personal communication; Carvalho, C.A. personal communication
[3] Das, S., P. Hell, and J. Huang, Chronological interval digraphsmanuscript; Das, S., P. Hell, and J. Huang, Chronological interval digraphsmanuscript · Zbl 1295.05161
[4] Feder, T., Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability, SIAM J. Discrete Math., 14, 471-480 (2001) · Zbl 0982.05097
[5] Feder, T.; Hell, P., List homomorphisms to reflexive graphs, J. Combinatorial Theory B, 72, 236-250 (1998) · Zbl 0904.05078
[6] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 487-505 (1999) · Zbl 0985.05048
[7] 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
[8] Feder, T., and P. Hell, The retraction and subretraction problems for reflexive digraphs; Feder, T., and P. Hell, The retraction and subretraction problems for reflexive digraphs
[9] Feder, T.; Hell, P.; Tucker-Nally, K., Digraph matrix partitions and trigraph homomorphisms, Discrete Applied Math., 154, 2458-2469 (2006) · Zbl 1106.05060
[10] Feder, T.; Madelaine, F.; Stewart, I. A., Dichotomies for classes of homomorphism problems involving unary functions, Theoretical Computer Science, 314, 1-43 (2004) · Zbl 1070.68133
[11] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM J. Computing, 28, 57-104 (1998) · Zbl 0914.68075
[12] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and interval graphs, Canadian J. Math., 16, 539-548 (1964) · Zbl 0121.26003
[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 Applied Math., 35, 29-45 (1992) · Zbl 0761.05040
[15] Hell, P., From graph colouring to constraint satisfaction: there and back again, (Topics in Discrete Mathematics. Topics in Discrete Mathematics, Springer Verlag Algorithms and Combinatorics Series, vol. 26 (2006)), 407-432 · Zbl 1116.05028
[16] Hell, P., and A. Rafiey, List homomorphisms to irreflexive digraphs; Hell, P., and A. Rafiey, List homomorphisms to irreflexive digraphs
[17] Hell, P., and A. Rafiey, Minimum cost homomorphisms to balanced and smooth digraphs; Hell, P., and A. Rafiey, Minimum cost homomorphisms to balanced and smooth digraphs · Zbl 1136.68462
[18] P. Hell and A. Rafiey, A new characterization of interval graphs; P. Hell and A. Rafiey, A new characterization of interval graphs
[19] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory B, 48, 92-110 (1990) · Zbl 0639.05023
[20] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[21] Hell, P.; Nešetřil, J.; Zhu, X., Complexity of tree homomorphisms, Discrete Applied Math., 70, 23-36 (1996) · Zbl 0868.05018
[22] Larose, B., Taylor operations on finite reflexive structures, International Journal of Mathematics and Computer Science, 1, 1-26 (2006) · Zbl 1100.08003
[23] Lekkerkerker, C. G.; Boland, J. C., Representation of a finite graph by a set of intervals on the real line, Fundamenta Math., 51, 45-64 (1962) · Zbl 0105.17501
[24] Müller, H., Recognizing interval digraphs and interval bigraphs in polynomial time, Discrete Appl. Math., 78, 189-205 (1997) · Zbl 0890.68103
[25] Papadimitriou, C.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall New York · Zbl 0503.90060
[26] Prisner, E., A characterization of interval catch digraphs, Discrete Math., 73, 285-289 (1989) · Zbl 0669.05038
[27] 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.