Paper Info
Title
Monotone Proper Interval Digraphs and Min-Max Orderings.
Abstract
We introduce a class of digraphs analogous to proper interval graphs and bigraphs. They are defined via a geometric representation by two inclusion-free families of intervals satisfying a certain monotonicity condition; hence we call them monotone proper interval digraphs. They admit a number of equivalent definitions, including an ordering characterization by so-called Min-Max orderings, and the existence of certain graph polymorphisms. Min-Max orderings arose in the study of minimum cost homomorphism problems: if H admits a a Min-Max ordering (or a certain extension of Min-Max orderings), then the minimum cost homomorphism problem to H is known to admit a polynomial time algorithm. We give a forbidden structure characterization of monotone proper interval digraphs, which implies a polynomial time recognition algorithm. This characterizes digraphs with a Min-Max ordering; we also similarly characterize digraphs with an extended Min-Max ordering. In a companion paper, we shall apply this latter characterization to derive a conjectured dichotomy classification for the minimum cost homomorphism problems-namely, we shall prove that the minimum cost homomorphism problem to a digraph that does not admit an extended Min-Max ordering is NP-complete.
Year
DOI
Venue
2012
10.1137/100783844
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
Field
DocType
interval digraphs,Min-Max orderings,forbidden structure characterizations,minimum cost homomorphisms
Monotonic function,Discrete mathematics,Graph,Bigraph,Combinatorics,Geometric representation,Homomorphism,Recognition algorithm,Time complexity,Monotone polygon,Mathematics
Journal
Volume
Issue
ISSN
26
4
0895-4801
Citations 
PageRank 
References 
2
0.36
0
Authors
2
Name
Order
Citations
PageRank
Pavol Hell12638288.75
Arash Rafiey233928.08