Narrow Results

Let $G=(V,E)$ be a simple graph with no isolated vertices. A dominating set $S$ of $G$ is said to be a cosecure dominating set of $G$, if for every vertex $v\in S$ there exists a vertex $u\in V\setminus S$ such that $uv\in E$ and $(S\setminus \{v\})\cup \{u\}$ is a dominating set of $G$. The Minimum Cosecure Domination problem is to find a minimum cardinality cosecure dominating set of $G$. In this paper, we show that the decision version of the problem is NP-complete for split graphs, undirected path graphs (subclasses of chordal graphs), and circle graphs. We also present a linear-time algorithm to compute the cosecure domination number of cographs (subclass of circle graphs). In addition, we present a few results on the approximation aspects of the problem.

Partition refinement techniques lead to simple and efficient algorithms for various applications: automaton minimization, string sorting … and also for algorithms on graphs. A generic algorithm that can be used for all these applications is presented and briefly discussed. Such an approach is interesting in an algorithmic tool kit perspective. New instances of the generic algorithm are presented: O(n+mlog n) very simple and practical algorithms for cographs recognition and for modular decomposition are designed. Although these algorithms are not linear, they are very easy to implement (as an instanciation of a generic procedure) and based on new ideas.

The intersection power graph of a finite group $G$ is a simple graph whose vertex set is $G$, in which two distinct vertices $x$ and $y$ are adjacent if and only if either one of $x$ and $y$ is the identity element, or $⟨x⟩\cap ⟨y⟩$ is non-trivial. A number of important graph classes, including cographs, chordal graphs, split graphs, and threshold graphs, can be defined either structurally or in terms of forbidden induced subgraphs. In this paper, we characterize the finite groups whose intersection power graphs are cographs, split graphs, and threshold graphs. We also classify the finite nilpotent groups whose intersection power graphs are chordal.

Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis. We introduce a novel and general search strategy that branches on the forbidden subgraphs of a graph class relaxation. By using the class of P₄-sparse graphs as the relaxed graph class, we obtain efficient bounded search tree algorithms for several parametrized deletion problems. We give the first non-trivial bounded search tree algorithms for the cograph edge-deletion problem and the trivially perfect edge-deletion problems. For the cograph vertex deletion problem, a refined analysis of the runtime of our simple bounded search algorithm gives a faster exponential factor than those algorithms designed with the help of complicated case distinctions and non-trivial running time analysis [R. Niedermeier and P. Rossmanith, An efficient fixed-parameter algorithm for 3-hitting set, J. Discrete Algorithms1(1) (2003) 89–102] and computer-aided branching rules [J. Gramm, J. Guo, F. Hüffner and R. Niedermeier, Automated generation of search tree algorithms for hard graph modification problems, Algorithmica39(4) (2004) 321–347].