DIMACS TR: 2004-30

k-Interval-filament graphs

Author: Fanica Gavril

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