|
|||||
- ARTHUR BUSCH, University of Dayton
Completion of colored graphs that avoid chordless cycles of prescribed lengths [PDF]
-
In this talk we consider a special case of graph sandwich problems typically referred to as colored completion problems. Given a property $\Pi$ and a graph $G$ with a proper vertex coloring, we ask whether one can find a supergraph of $G$ with property $\Pi$ that remains properly colored. We completely classify, in terms of the number of colors used, the complexity of the $(C_4, C_5, \dots, C_{s+4})$-free colored completion problem and and the $(C_4, C_6, \dots, C_{2s+4})$-free colored completion problem for all fixed $s \ge 0$. These classifications are related to the colored completion problem for chordal graphs, which is NP-complete when the number of colors is part of the input but solvable in polynomial time when the number of colors is fixed, and to the even-hole-free colored completion problem, whose complexity is not known.
This is joint work with R. Sritharan, University of Dayton Department of Computer Science.
- KEVIN HSU, University of Victoria
Minimal obstructions for local tournament orientation completions [PDF]
-
A local tournament is an oriented graph D in which the in-neighbourhood as well as the out-neighbourhood of each vertex induces a tournament; if the in-neighbourhood as well as the out-neighbourhood of each vertex induces a transitive tournament, then D is called a local transitive tournament. The orientation completion problem for local (transitive) tournaments asks whether a partially oriented graph G can be completed to a local (transitive) tournament by orienting the (non-oriented) edges in G. It is proved recently that the orientation completion problem is polynomial time solvable for local tournaments and NP-complete for local transitive tournaments. We characterize minimal partially oriented graphs that cannot be completed to local tournaments. Our results combine structural theorems on local tournaments and their underlying proper circular arc graphs. This work is joint with Jing Huang.
- ARTI PANDEY, Indian Institute of Technology Ropar, INDIA
Complexity of Semitotal Domination in Graphs [PDF]
-
For a graph G=(V,E), a set D subset of V is called a semitotal dominating set of G if (i) every vertex not in D is adjacent to atleast one vertex in D, and (ii) every vertex in D is within distance 2 of another vertex of D. The Minimum Semitotal Domination problem is to find a semitotal dominating set of minimum cardinality. Given a graph G and a positive integer k, the Semitotal Domination Decision problem is to decide whether G has a semitotal dominating set of cardinality at most k. In this paper, we discuss several algorithmic results for this problem. We show that the Semitotal Domination Decision problem remains NP-complete for chordal graphs, split graphs, undirected path graphs and planar graphs. We also present polynomial time algorithms to solve the Minimum Semitotal Domination problem for interval graphs and circular-arc graphs.
- AKBAR RAFIEY, Simon Fraser University
On approximation of H-coloring [PDF]
-
The minimum cost homomorphism problem (MinHOM) is a natural optimization problem for homomorphisms to a fixed (di)graph H (a.k.a H-coloring). Given an input (di)graph G, with a cost associated with mapping any vertex of G to any vertex of H, one seeks to minimize the sum of costs of the assignments over all homomorphisms of G to H.
We are interested in the approximation of MinHOM within a constant factor. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph. For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs and k-arc digraphs. Specifically, we have:
1-Dichotomy for Graphs: MinHOM(H) has a $2|V(H)|$-approximation algorithm if graph H is a bi-arc graph, otherwise, it is inapproximable;
2- MinHOM(H) has a $|V(H)|^2$-approximation algorithm if H is a bi-arc digraph;
3- MinHOM(H) has a $|V(H)|^2$-approximation algorithm if H is a k-arc digraph.
- YINFENG ZHU, Shanghai Jiao Tong University, China
Strong digraph homomorphisms and non-liftable indices [PDF]
-
Let $\phi$ be a homomorphism from a digraph $G$ to a digraph $H$. A walk $a_1,\ldots, a_k$ in $G$ is called a lifting along $\phi$ of a walk $e_1, \ldots, e_k$ in $H$ if $e_i = \phi(a_i)$ for all $i \in [1,k]$. We call $\phi$ a strong homomoprhism if every walk in $H$ has a lifting in $G$. If $\phi$ is non-strong, the length of a shortest walk in $H$ without any lifting along $\phi$, denoted by $\delta(\phi)$, is called the non-liftable index of $\phi$.
We show that it is NP-complete to decide whether or not $\phi$ is strong and, on the additional condition that $G$ and $H$ are strongly connected and have the same spectral radius, there is an algorithm to determine whether or not $\phi$ is strong in $O(|V_G|^3)$ time. We also prove that
the largest non-liftable index among all non-strong homomorphisms from an $n$-vertex digraph equals $2^n-1$.