Let S be an independent set of a simple undirected graph G. Suppose that each vertex of S has a token placed on it. The tokens are allowed to be moved, one at a time, by sliding along the edges of G while maintaining the property that after each move, the vertices having tokens always form an independent set of G. We would like to determine whether the tokens can be eventually brought to stay on the vertices of another independent set S' of G in this manner. In other words, we would like to decide if we can transform S into S' through a sequence of steps, each of which involves substituting a vertex in the current independent set with one of its neighbours to obtain another independent set. This problem of determining if one independent set of a graph "is reachable" from another independent set of it is known to be PSPACE-hard even for split graphs, planar graphs, and graphs of bounded treewidth. Polynomial time algorithms have been obtained for certain graph classes like trees, interval graphs, claw-free graphs, and bipartite permutation graphs. We present a polynomial time algorithm for the problem on block graphs, which are the graphs in which every maximal 2-connected subgraph is a clique. Our algorithm is the first generalization of the known polynomial time algorithm for trees to a larger class of graphs.

Given a digraph $G$, a set $X\subseteq V(G)$ is said to be absorbing set (resp. dominating set) if every vertex in the graph is either in $X$ or is an in-neighbour (resp. out-neighbour) of a vertex in $X$. A set $S\subseteq V(G)$ is said to be an independent set if no two vertices in $S$ are adjacent in $G$. A kernel (resp. solution) of $G$ is an independent and absorbing (resp. dominating) set in $G$. We explore the algorithmic complexity of these problems in the well known class of interval digraphs. A digraph $G$ is an interval digraph if a pair of intervals $(S_u,T_u)$ can be assigned to each vertex $u$ of $G$ such that $(u,v)\in E(G)$ if and only if $S_u\cap T_v\neq\emptyset$. Many different subclasses of interval digraphs have been defined and studied in the literature by restricting the kinds of pairs of intervals that can be assigned to the vertices. We observe that several of these classes, like interval catch digraphs, interval nest digraphs, adjusted interval digraphs and chronological interval digraphs, are subclasses of the more general class of reflexive interval digraphs -- which arise when we require that the two intervals assigned to a vertex have to intersect. We show that all the problems mentioned above are efficiently solvable, in most of the cases even linear-time solvable, in the class of reflexive interval digraphs, but are APX-hard on even the very restricted class of interval digraphs called point-point digraphs, where the two intervals assigned to each vertex are required to be degenerate, i.e. they consist of a single point each. The results we obtain improve and generalize several existing algorithms and structural results for subclasses of reflexive interval digraphs.

A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic, Hirst, and Lewenstein [ Algorithmica, 31 (2001), pp. 139--154]. Our algorithm actually solves the more general problem of computing a maximum cardinality “weak independent set” in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.

An instance of the $(n-k)$-Set Cover or the $(n-k)$-Test Cover problems is of the form $(\mathcal{U},\mathcal{S},k)$, where $\mathcal{U}$ is a set with $n$ elements, $\mathcal{S}\subseteq 2^\mathcal{U}$ with $|\mathcal{S}|=m$, and $k$ is the parameter. The instance is a Yes-instance of $(n-k)$-Set Cover if and only if there exists $\mathcal{S}'\subseteq\mathcal{S}$ with $|\mathcal{S}'|\leq n-k$ such that every element of $\mathcal{U}$ is contained in some set in $\mathcal{S}'$. Similarly, it is a Yes-instance of $(n-k)$-Test Cover if and only if there exists $\mathcal{S}'\subseteq\mathcal{S}$ with $|\mathcal{S}'|\leq n-k$ such that for any pair of elements from $\mathcal{U}$, there exists a set in $\mathcal{S}'$ that contains one of them but not the other. It is known in the literature that both $(n-k)$-Set Cover and $(n-k)$-Test Cover do not admit polynomial kernels (under some well-known complexity theoretic assumptions). However, in this paper we show that they do admit “partially polynomial kernels”: we give polynomial time algorithms that take as input an instance $(\mathcal{U},\mathcal{S},k)$ of $(n-k)$-Set Cover (respectively, $(n-k)$-Test Cover) and return an equivalent instance $(\tilde{\mathcal{U}},\tilde{\mathcal{S}}, \tilde{k})$ of $(n-k)$-Set Cover (respectively, $(n-k)$-Test Cover) with $\tilde{k} \leq k$ and $| \tilde{\mathcal{U}}|= \mathcal{O}(k^2)$ (respectively, $|\tilde{\mathcal{U}}|=\mathcal{O}(k^7)$). These results allow us to generalize, improve, and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain “sparsity properties.” Using a part of our partial kernelization algorithm for $(n-k)$-Set Cover, we also get an improved fixed-parameter tractable algorithm for this problem which runs in time $\mathcal{O}(4^kk^{\mathcal{O}(1)}(m+n)+mn)$ improving over the previous best of $\mathcal{O}(8^{k+o(k)}(m+n)^{\mathcal{O}(1)})$. On the other hand, the partially polynomial kernel for $(n-k)$-Test Cover gives an algorithm with running time $\mathcal{O}(2^{\mathcal{O}(k^2)}(m+n)^{\mathcal{O}(1)})$. We believe such an approach could also be useful for other covering problems.

A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomial-time certifying recognition algorithm is known to date, despite such algorithms being found for many subclasses of circular-arc graphs. This is largely due to the fact that a forbidden structure characterization of circular-arc graphs is not known, even though the problem has been intensely studied since the seminal work of Klee in the 1960s. In this contribution, we settle this problem. We present the first forbidden structure characterization of circular-arc graphs. Our obstruction has the form of mutually avoiding walks in the graph. It naturally extends a similar obstruction that characterizes interval graphs. As a consequence, we give the first polynomial-time certifying algorithm for the recognition of circular-arc graphs.

Finding a forbidden subgraph characterization of circular-arc graphs is a challenging open problem. Many partial results toward this goal have been proposed over the years, but a satisfactory answer has so far eluded us. In this paper, we suggest a new direction in this line of research. We propose a novel structural obstruction to circular-arc graphs---a blocking quadruple---and study its use in characterizing circular-arc graphs within chordal graphs. Notably, we observe that the absence of blocking quadruples unifies characterizations of various known chordal subclasses of circular-arc graphs found in the literature. To this end, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples and show that the absence of blocking quadruples exactly characterizes chordal circular-arc graphs of independence number 4 or less. Our proof uses an interesting geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree. In fact, we prove that this characterizes circular-arc representability of all chordal graphs.

In a typical covering problem we are given a universe U of size n, a family S (S could be given implicitly) of size m and an integer k and the objective is to check whether there exists a subfamily S' \subseteq S of size at most k satisfying some desired properties. If S' is required to contain all the elements of U then it corresponds to the classical Set Cover problem. On the other hand if we require S' to satisfy the property that for every pair of elements x,y \in U there exists a set S \in S' such that |S \cap {x,y}|=1 then it corresponds to the Test Cover problem. In this paper we consider a natural parameterization of Set Cover and Test Cover. More precisely, we study the (n-k)-Set Cover and (n-k)-Test Cover problems, where the objective is to find a subfamily S' of size at most n-k satisfying the respective properties, from the kernelization perspective. It is known in the literature that both (n-k)-Set Cover and (n-k)-Test Cover do not admit polynomial kernels (under some well known complexity theoretic assumptions). However, in this paper we show that they do admit "partially polynomial kernels". More precisely, we give polynomial time algorithms that take as input an instance (U,S,k) of (n-k)-Set Cover (n-k)-Test Cover) and return an equivalent instance (~U,~S,~k) of (n-k)-Set Cover (respectively (n-k)-Test Cover) with ~k <= k and |~U|= O(k^2) (|~U|=O(k^7)). These results allow us to generalize, improve and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain "sparsity properties". Using a part of our kernelization algorithm for (n-k)-Set Cover, we also get an improved FPT algorithm for this problem which runs in time O(4^k*k^{\O(1)}*(m+n)) improving over the previous best of O(8^{k+o(k)}*(m+n)^{O(1)}). On the other hand the partially polynomial kernel for (n-k)-Test Cover implies the first single exponential FPT algorithm, an algorithm with running time O(2^{O(k^2)}*(m+n)^{O(1)}). We believe such an approach will also be useful for other covering problems as well.

We prove that every planar graph has a representation using axis-parallel cubes in three dimensions in such a way that there is a cube corresponding to each vertex of the planar graph and two cubes have a non-empty intersection if and only if their corresponding vertices are adjacent. Moreover, when two cubes have a non-empty intersection, they just touch each other. This result is a strengthening of a result by Thomassen which states that every planar graph has such a representation using axis-parallel boxes.