A graph H is an induced minor of G if there exists an induced minor model of H in G , that is, a collection of pairwise disjoint subsets of vertices of G labeled by the vertices of H , each inducing a connected subgraph in G , such that two vertices of H are adjacent if and only if there is an edge in G between the corresponding subsets. In this paper, we investigate structural properties of induced minor models, including bounds on treewidth and chromatic number of the subgraphs induced by minimal induced minor models. As algorithmic applications of our structural results, we make use of recent developments regarding tree-independence number to show that if H is the 4-wheel, the 5-vertex complete graph minus an edge, or a complete bipartite graph K 2 , q , then there is a polynomial-time algorithm to find in a given graph G an induced minor model of H in G , if there is one. We also develop an alternative polynomial-time algorithm for recognizing graphs that do not contain K 2 , 3 as an induced minor, which revolves around the idea of detecting the induced subgraphs whose presence is forced when the input graph contains K 2 , 3 as an induced minor. It turns out that all these induced subgraphs are Truemper configurations.

The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP -hard graph problems, like maximum-weight independent set, can be solved in time \(n^{\mathcal{O}(k)}\) if the input \( n \) -vertex graph is given together with a tree decomposition of independence number \( k \) . Yolov, in SODA 2018, gave an algorithm that, given an \( n \) -vertex graph \( G \) and an integer \( k \) , in time \(n^{\mathcal{O}(k^{3})}\) either constructs a tree decomposition of \( G \) whose independence number is \(\mathcal{O}(k^{3})\) or correctly reports that the tree-independence number of \( G \) is larger than \( k \) . In this article, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time \(2^{\mathcal{O}(k^{2})}n^{\mathcal{O}(k)}\) and either outputs a tree decomposition of \( G \) with independence number at most \(8k\) or determines that the tree-independence number of \( G \) is larger than \( k \) . This implies \(2^{\mathcal{O}(k^{2})}n^{\mathcal{O}(k)}\) -time algorithms for various problems, like maximum-weight independent set, parameterized by the tree-independence number \( k \) without needing the decomposition as an input. Assuming Gap-ETH, an \(n^{\Omega(k)}\) factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP -hard: We show that for every constant \(k\geq 4\) it is NP -complete to decide whether a given graph has the tree-independence number at most \( k \) .

The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum weight independent set, can be solved in time n^{O(k)} if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov, in [SODA 2018], gave an algorithm that, given an n-vertex graph G and an integer k, in time n^{O(k^3)} either constructs a tree decomposition of G whose independence number is O(k^3) or correctly reports that the tree-independence number of G is larger than k. In this paper, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time 2^{O(k^2)} n^{O(k)} and either outputs a tree decomposition of G with independence number at most $8k$, or determines that the tree-independence number of G is larger than k. This implies 2^{O(k^2)} n^{O(k)}-time algorithms for various problems, like maximum weight independent set, parameterized by the tree-independence number k without needing the decomposition as an input. Assuming Gap-ETH, an n^{Ω(k)} factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k \ge 4 it is NP-hard to decide if a given graph has the tree-independence number at most k.

For an integer k ≥ 2, a k-community structure in an undirected graph is a partition of its vertex set into k sets called communities, each of size at least two, such that every vertex of the graph has proportionally at least as many neighbours in its own community as in any other community. In this paper, we give a necessary and sufficient condition for a forest on n vertices to admit a k-community structure. Furthermore, we provide an O(k2 ・ n2)-time algorithm that computes such a k-community structure in a forest, if it exists. These results extend a result of Bazgan et al., 2018. We also show that if communities are allowed to have size one, then every forest with n ≥ k ≥ 2 vertices admits a k-community structure that can be found in time O(k2 ・ n2). We then consider threshold graphs and show that every connected threshold graph admits a 2-community structure if and only if it is not isomorphic to a star; also if such a 2-community structure exists, we explain how to obtain it in linear time. We further describe an infinite family of disconnected threshold graphs, containing exactly one isolated vertex, that do not admit any 2-community structure. Finally, we present a new infinite family of connected graphs that may contain an even or an odd number of vertices without 2-community structures, even if communities are allowed to have size one.

This paper studies the allocation of indivisible items to agents, when each agent’s preferences are expressed by means of a directed acyclic graph. The vertices of each preference graph represent the subset of items approved of by the respective agent. An arc (a,b) in such a graph means that the respective agent prefers item a over item b. We introduce a new measure of dissatisfaction of an agent by counting the number of non-assigned items which are approved of by the agent and for which no more preferred item is allocated to the agent. Considering two problem variants, we seek an allocation of the items to the agents in a way that minimizes (i) the total dissatisfaction over all agents or (ii) the maximum dissatisfaction among the agents. For both optimization problems we study the status of computational complexity and obtain NP-hardness results as well as polynomial algorithms with respect to natural underlying graph structures, such as stars, trees, paths, and matchings. We also analyze the parameterized complexity of the two problems with respect to various parameters related to the number of agents, the dissatisfaction threshold, the vertex degrees of the preference graphs, and the treewidth.

Moplexes are natural graph structures that arise when lifting Dirac’s classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes such as interval graphs, claw-free, and diamond-free graphs. However, while every non-complete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is, among others, motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are interval. In this work we initiate an investigation of k-moplex graphs, which are defined as graphs containing at most k moplexes. Of particular interest is the smallest nontrivial case, k = 2, which forms a counterpart to the class of interval graphs. As our main structural result, we show that the class of connected 2-moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs; moreover, both inclusions are tight for hereditary classes. From a complexity theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely Graph Isomorphism and Max-Cut. Furthermore, for graphs with a higher number of moplexes, we lift the previously known result that graphs without asteroidal triples have at most two moplexes to the more general setting of larger asteroidal sets. We also discuss sufficient conditions for the existence of Hamiltonian paths in 2-moplex graphs as well as connections with avoidable vertices.

In the Token Jumping problem we are given a graph $$G = (V,E)$$ and two independent sets S and T of G, each of size $$k \ge 1$$ . The goal is to determine whether there exists a sequence of k-sized independent sets in G, $$\langle S_0, S_1, \ldots , S_\ell \rangle$$ , such that for every i, $$|S_i| = k$$ , $$S_i$$ is an independent set, $$S = S_0$$ , $$S_\ell = T$$ , and $$|S_i \varDelta S_{i+1}| = 2$$ . In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of G, then the problem asks for a sequence of independent sets which transforms S to T by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACE-complete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixed-parameter tractable on $$C_4$$ -free bipartite graphs when parameterized by k. For Token Jumping, we in fact show that the problem admits a polynomial kernel on $$\{C_3,C_4\}$$ -free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant $$p \ge 4$$ , both problems are W[1]-hard on $$\{C_4, \dots , C_p\}$$ -free graphs and Token Sliding remains W[1]-hard even on bipartite graphs.

Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes closed under taking induced subgraphs in which this condition is also sufficient, which we call $({tw},\omega)$-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and $k$-coloring problems. We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs $H$ for which the class of graphs excluding $H$ is $({tw},\omega)$-bounded. Our results yield an infinite family of $\chi$-bounded induced-minor-closed graph classes and imply that the class of 1-perfectly orientable graphs is $({tw},\omega)$-bounded, leading to linear-time algorithms for $k$-coloring 1-perfectly orientable graphs for every fixed $k$. This answers a question of Brešar, Hartinger, Kos, and Milanič from 2018 and one of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019, respectively. We also reveal some further algorithmic implications of $({tw},\omega)$-boundedness related to list $k$-coloring and clique problems. In addition, we propose a question about the complexity of the maximum weight independent set problem in $({tw},\omega)$-bounded graph classes and prove that the problem is polynomial-time solvable in every class of graphs excluding a fixed star as an induced minor.

A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph $G$ and an integer $p$, the Colourful Components problem asks whether there exist at most $p$ edges whose removal makes $G$ colourful and the Colourful Partition problem asks whether there exists a partition of $G$ into at most $p$ colourful components. In order to refine our understanding of the complexity of the problems on trees, we study both problems on $k$-caterpillars, which are trees with a central path $P$ such that every vertex not in $P$ is within distance $k$ from a vertex in $P$. We prove that Colourful Components and Colourful Partition are NP-complete on $4$-caterpillars with maximum degree $3$, $3$-caterpillars with maximum degree $4$ and $2$-caterpillars with maximum degree $5$. On the other hand, we show that the problems are linear-time solvable on $1$-caterpillars. Hence, our results imply two complexity dichotomies on trees: Colourful Components and Colourful Partition are linear-time solvable on trees with maximum degree $d$ if $d \leq 2$ (that is, on paths), and NP-complete otherwise; Colourful Components and Colourful Partition are linear-time solvable on $k$-caterpillars if $k \leq 1$, and NP-complete otherwise. We leave three open cases which, if solved, would provide a complexity dichotomy for both problems on $k$-caterpillars, for every non-negative integer $k$, with respect to the maximum degree. We also show that Colourful Components is NP-complete on $5$-coloured planar graphs with maximum degree $4$ and on $12$-coloured planar graphs with maximum degree $3$. Our results answer two open questions of Bulteau et al. mentioned in [30th Annual Symposium on Combinatorial Pattern Matching, 2019].