Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms

详细信息	查看全文 | 推荐本文 |

• 作者：Tomá ; s Feder^a ; ^{tomas@theory.Stanford.edu} ; Pavol Hell^b ; ^{pavol@cs.sfu.ca} ; Jing Huang^c ; ¹ ; ^{jing@math.uvic.ca} ; Arash Rafiey^d ; ^{arash@idsia.ch}
• 关键词：Interval graphs ; Interval digraphs ; Adjusted interval digraphs ; Forbidden structure characterizations ; Polynomial algorithms ; List homomorphism problems ; Dichotomy
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：April, 2012
• 卷：160
• 期：6
• 页码：697-707
• 文件大小：278 K

摘要

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 鈥榓djusted interval digraphs鈥? By contrast, for these digraphs we exhibit a natural forbidden structure characterization, in terms of a novel structure which we call an 鈥榠nvertible 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鈥攖he 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 is a reflexive undirected graph, the list homomorphism problem LHOM() is polynomial if is an interval graph, and NP-complete otherwise. If is a reflexive digraph, LHOM() is polynomial if 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.