Search

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh et al. [5] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles the small conjecture [8] in the case of ordered graphs. [ABSTRACT FROM AUTHOR]

Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been further extended to binary structures, in several (basically equivalent) ways. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a proper permutation class. As a by-product, we show that every class with bounded twin-width contains at most 2O(n) pairwise non-isomorphic n-vertex graphs. [ABSTRACT FROM AUTHOR]

In the TOKEN SWAPPING problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that TOKEN SWAPPING is W[1]-hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k)no(k/logk) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial nO(k)-time algorithm. We also consider two generalizations of the TOKEN SWAPPING, namely COLORED TOKEN SWAPPING (where the tokens have colors and tokens of the same color are indistinguishable), and SUBSET TOKEN SWAPPING (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, SUBSET TOKEN SWAPPING, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases. [ABSTRACT FROM AUTHOR]

The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of Grundy Coloring , the problem of determining whether a given graph has Grundy number at least k . We also study the variants Weak Grundy Coloring (where the coloring is not necessarily proper) and Connected Grundy Coloring (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that Grundy Coloring can be solved in time O ∗ ( 2 . 44 3 n ) and Weak Grundy Coloring in time O ∗ ( 2 . 71 6 n ) on graphs of order n . While Grundy Coloring and Weak Grundy Coloring are known to be solvable in time O ∗ ( 2 O ( w k ) ) for graphs of treewidth w (where k is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time O ∗ ( 2 o ( w log w ) ) . We also describe an O ∗ ( 2 2 O ( k ) ) algorithm for Weak Grundy Coloring , which is therefore FPT for the parameter k . Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for Grundy Coloring ). Although we do not know whether Grundy Coloring is in FPT , we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for Grundy Coloring and Weak Grundy Coloring on apex-minor graphs. In stark contrast with the two other problems, we show that Connected Grundy Coloring is NP -complete already for k = 7 colors. [ABSTRACT FROM AUTHOR]

The Graph Motif problem was introduced in 2006 in the context of biological networks. It consists of deciding whether or not a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Graph Motif has been mostly analyzed from the standpoint of parameterized complexity. The main parameters which came into consideration were the size of the multiset and the number of colors. In the many utilizations of Graph Motif , however, the input graph originates from real-life applications and has structure. Motivated by this prosaic observation, we systematically study its complexity relatively to graph structural parameters. For a wide range of parameters, we give new or improved FPT algorithms, or show that the problem remains intractable. For the FPT cases, we also give some kernelization lower bounds as well as some ETH-based lower bounds on the worst case running time. Interestingly, we establish that Graph Motif is W[1] -hard (while in W[P] ) for parameter max leaf number, which is, to the best of our knowledge, the first problem to behave this way. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of a broad class of problems called 'local graph partitioning problems' that includes the classical fixed cardinality problems as max $$k$$ - vertex cover, $$k$$ - densest subgraph, etc. By developing a technique that we call 'greediness-for-parameterization', we obtain fixed parameter algorithms with respect to a pair of parameters $$k$$ , the size of the solution (but not its value) and $$\varDelta $$ , the maximum degree of the input graph. In particular, greediness-for-parameterization improves asymptotic running times for these problems upon random separation (that is a special case of color coding) and is more intuitive and simple. Then, we show how these results can be easily extended for getting standard-parameterization results (i.e., with parameter the value of the optimal solution) for a well known local graph partitioning problem. [ABSTRACT FROM AUTHOR]