Abstract Frei et al. (J. Comput. Syst. Sci. 123, 103–121, 2022) show that the stability, vertex stability, and unfrozenness problems with respect to certain graph parameters are complete for $$\varvec{\Theta _{2}^{\textrm{P}}}$$ Θ 2 P , the class of problems solvable in polynomial time by parallel access to an NP oracle. They studied the common graph parameters $$\varvec{\alpha }$$ α (the independence number), $$\varvec{\beta }$$ β (the vertex cover number), $$\varvec{\omega }$$ ω (the clique number), and $$\varvec{\chi }$$ χ (the chromatic number). We complement their approach by providing polynomial-time algorithms solving these problems for special graph classes, namely for graphs with bounded tree-width or bounded clique-width. In order to improve these general time bounds even further, we then focus on trees, forests, bipartite graphs, and co-graphs.

Abstract Computing the directed path-width of a directed graph is an NP-hard problem. Even for digraphs of maximum semi-degree 3 the problem remains hard. We propose a decomposition of an input digraph G = (V,A) by a number k of sequences with entries from V, such that (u,v) ∈ A if and only if in one of the sequences there is an occurrence of u appearing before an occurrence of v. We present several graph theoretical properties of these digraphs. Among these we give forbidden subdigraphs of digraphs which can be defined by k = 1 sequence, which is a subclass of semicomplete digraphs. Given the decomposition of digraph G, we show an algorithm which computes the directed path-width of G in time $\mathcal {O}(k\cdot (1+N)^{k})$ O ( k ⋅ ( 1 + N ) k ) , where N denotes the maximum sequence length. This leads to an XP-algorithm w.r.t. k for the directed path-width problem. Our result improves the algorithms of Kitsunai et al. for digraphs of large directed path-width which can be decomposed by a small number of sequences and confirm their conjecture that semicompleteness is a useful restriction when considering digraphs.

Luttamguzi et al. [(2005) Integer Programming Methods for Several Optimization Problems in Graph Theory. Proc. Int. Conf. Computers and Their Applications, CATA 2005, New Orleans, LA, USA, March 16–18, pp. 50–55. ISCA] have introduced a useful framework for the formulation of graph layout parameters measuring number of edges, which is applied to give linear programming formulations for computing the cut-width, minimum linear arrangement and band-width of a graph. We extend the framework of Luttamguzi et al. by the efficient formulation of sets of vertices of the same neighborhood—so-called groups—using binary linear programming (BIP) conditions. We apply our methods in order to find first BIP formulations for computing the important graph layout para-me-ters path-width, neighborhood-width, linear NLC-width, and linear clique-width. Our formulations give useful and new characterizations of the problems as well as easy-to-understand algorithms for their solution. The size of our formulations is polynomial in the size of the input graph.