Search

We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva (Algorithmica 80(1), 104–115, 2018) and Bonomo et al. (Graphs and Combinatorics 25(2), 153–167, 2009). This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b -Coloring and Fall Coloring are tight under the Exponential Time Hypothesis. [ABSTRACT FROM AUTHOR]

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP -complete on general graphs if k is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on O (k 2) vertices. [ABSTRACT FROM AUTHOR]

While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions towards a better understanding of the algorithmic treatment of intersection digraphs. First, we introduce natural classes of intersection digraphs that generalize several classes studied in the literature. Second, we define the directed locally checkable vertex (DLCV) problems, which capture many well‐studied problems on digraphs, such as (Independent) Dominating Set, Kernel, and H $H$‐Homomorphism. Third, we give a new width measure of digraphs, bi‐mim‐width, and show that the DLCV problems are polynomial‐time solvable when we are provided a decomposition of small bi‐mim‐width. Fourth, we show that several classes of intersection digraphs have bounded bi‐mim‐width, implying that we can solve all DLCV problems on these classes in polynomial time given an intersection representation of the input digraph. We identify reflexivity as a useful condition to obtain intersection digraph classes of bounded bi‐mim‐width, and therefore to obtain positive algorithmic results. [ABSTRACT FROM AUTHOR]

In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in polynomial time. [ABSTRACT FROM AUTHOR]

A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with q colors. For fixed q ≥ 2 , we give an O ⋆ (q tw) -time algorithm when the input graph is given together with one of its tree decompositions of width tw . We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is XP parameterized by clique-width. [ABSTRACT FROM AUTHOR]

We give a first polynomial-time algorithm for (Weighted) Feedback Vertex Set on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an n O (w) -time algorithm that solves Feedback Vertex Set. This provides a unified polynomial-time algorithm for many well-known classes, such as Interval graphs, Permutation graphs, and Leaf power graphs (given a leaf root), and furthermore, it gives the first polynomial-time algorithms for other classes of bounded mim-width, such as Circular Permutation and Circular k-Trapezoid graphs (given a circular k-trapezoid model) for fixed k. We complement our result by showing that Feedback Vertex Set is W [ 1 ] -hard when parameterized by w and the hardness holds even when a linear branch decomposition of mim-width w is given. [ABSTRACT FROM AUTHOR]

In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in k + r for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of 'base' solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest. [ABSTRACT FROM AUTHOR]