## DIMACS TR: 2004-30

##
k-Interval-filament graphs

### Author: Fanica Gavril

**
ABSTRACT
**
For a fixed $k$, an oriented graph is $k-transitive$
if it is acyclic and for every directed path $p=u1->
u2-> ...->uk+2$
with $k+2$ vertices, $p$ induces a clique if each of the
two subpaths $u1->u2->...->uk+1$
and $u2->...->uk+2$
induces a clique. We describe an algorithm to find a maximum
weight clique in a $k$-transitive graph.
Consider a hereditary family $G$ of graphs.
A graph $H(V,E)$ is called $G-k-mixed$ if its edge
set can be partitioned into two disjoint subsets $E1$, $E2-E3$
such that $H(V,E1) \in $G$,
$H(V,E2)$ is transitive, $H(V,E2-E3)$ is $k$-transitive
and for every three distinct vertices $u,v,w$ if $u->v
\in E2$
and $(v,w) \in E1$ then
$(u,w) \in E1$. The letter
$G$ is generic and can be replaced by names of specific
families. We show that if the family $G$ has a polynomial
time algorithm to find a maximum clique, then, under certain
restrictions there exists a polynomial time algorithm to find a
maximum clique in a family of $G-k$-mixed graphs.

Let $I$ be a family of intervals on a line $L$
in a plane $PL$ such that every two intersecting intervals have
a common segment. In $PL$, above $L$, construct to each
interval $i(v) \in I$ a
filament $v $connecting its two endpoints, such that for every
two filaments $u,v$ having $u \bigcap v \not = empty_set $
and disjoint intervals $i(u)<i(v)$, there are no $k$
filaments $w$ with $i(u)<i(w)<i(v)$ which
intersect neither $u$ nor $v$, are mutually disjoint and
have mutually disjoint intervals. This is a $family of
k-interval-filaments$ and its intersection graph is a
$k-interval-filament graph$; their complements are
($k$-transitive) mixed graphs and have a polynomial time
algorithm for maximum cliques. Now, when two filaments $u,v$ do
not intersect because $u \subset v$,
and between $u$ and $v$ there are at most $k-1$
non-intersecting filaments $w1,...,wk-1$
such that $wi \subset wi+1$
and intersect neither $u$ nor $v$, we attach to each one of
$u,v$ a branch in the space above $PL$ such that the two
branches intersect. This is a$ family of
general-k-interval-filaments$ and its intersection graph is a
$general-k-interval-filament graph$; their complements are
($k$-transitive)-$k$-mixed graphs.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-30.pdf

DIMACS Home Page