Generalised hypertree width ($ghw$) is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing $ghw$ of a hypergraph is notoriously hard. The decision version of the problem, checking whether $ghw(H) \leq k$, is paraNP-hard when parameterised by $k$. Furthermore, approximation of $ghw$ is at least as hard as approximation of Set-Cover, which is known to not admit any fpt approximation algorithms. Research in the computation of ghw so far has focused on identifying structural restrictions to hypergraphs -- such as bounds on the size of edge intersections -- that permit XP algorithms for $ghw$. Yet, even under these restrictions that problem has so far evaded any kind of fpt algorithm. In this paper we make the first step towards fpt algorithms for $ghw$ by showing that the parameter can be approximated in fpt time for graphs of bounded edge intersection size. In concrete terms we show that there exists an fpt algorithm, parameterised by $k$ and $d$, that for input hypergraph $H$ with maximal cardinality of edge intersections $d$ and integer $k$ either outputs a tree decomposition with $ghw(H) \leq 4k(k+d+1+)(2k-1)$, or rejects, in which case it is guaranteed that $ghw(H) > k$. Thus, in the special case, of hypergraphs of bounded edge intersection, we obtain an fpt $O(k^3)$-approximation algorithm for $ghw$.

Abstract. Given two [Formula: see text]-vertex graphs [Formula: see text] and [Formula: see text] of bounded treewidth, is there an [Formula: see text]-vertex graph [Formula: see text] of bounded treewidth having subgraphs isomorphic to [Formula: see text] and [Formula: see text]? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if [Formula: see text] is a binary tree and [Formula: see text] is a ternary tree. We also provide an extensive study of cases where such “gluing” is possible. In particular, we prove that if [Formula: see text] has treewidth [Formula: see text] and [Formula: see text] has pathwidth [Formula: see text], then there is an [Formula: see text]-vertex graph of treewidth at most [Formula: see text] containing both [Formula: see text] and [Formula: see text] as subgraphs.

Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. We show how this combinatorial result can be used to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤k for some constant k. Moreover, we show a dual version of our main result for fractional hitting sets.

We introduce a new graph parameter called linear upper maximum induced matching width lu-mim width, denoted for a graph G by lu(G). We prove that the smallest size of the obdd for φ, the monotone 2-cnf corresponding to G, is sandwiched between 2^{lu(G)} and n^{O(lu(G))}. The upper bound is based on a combinatorial statement that might be of an independent interest. We show that the bounds in terms of this parameter are best possible. The new parameter is closely related to two existing parameters: linear maximum induced matching width (lmim width) and linear special induced matching width (lsim width). We prove that lu-mim width lies strictly in between these two parameters, being dominated by lsim width and dominating lmim width. We conclude that neither of the two existing parameters can be used instead of lu-mim width to characterize the size of obdds for monotone 2-cnfs and this justifies introduction of the new parameter.

Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Every hypergraph H has a width relative to each of these methods: its hypertree width hw(H) , its generalized hypertree width ghw(H) , and its fractional hypertree width fhw(H) , respectively. It is known that hw(H)≤ k can be checked in polynomial time for fixed k , while checking ghw(H)≤ k is NP-complete for k ≥ 3 . The complexity of checking fhw(H)≤ k for a fixed k has been open for over a decade. We settle this open problem by showing that checking fhw(H)≤ k is NP-complete, even for k=2 . The same construction allows us to prove also the NP-completeness of checking ghw(H)≤ k for k=2 . After that, we identify meaningful restrictions that make checking for bounded ghw or fhw tractable or allow for an efficient approximation of the fhw .

An extremal point of a positive threshold Boolean function $f$ is either a maximal zero or a minimal one. It is known that if $f$ depends on all its variables, then the set of its extremal points completely specifies $f$ within the universe of threshold functions. However, in some cases, $f$ can be specified by a smaller set. The minimum number of points in such a set is the specification number of $f$. Hu (1965) showed that the specification number of a threshold function of $n$ variables is at least $n+1$. Anthony et al. (1995) proved that this bound is attained for nested functions and conjectured that for all other threshold functions the specification number is strictly greater than $n+1$. In the present paper, we resolve this conjecture negatively by exhibiting threshold Boolean functions of $n$ variables, which are non-nested and for which the specification number is $n+1$. On the other hand, we show that the set of extremal points satisfies the statement of the conjecture, i.e.~a positive threshold Boolean function depending on all its $n$ variables has $n+1$ extremal points if and only if it is nested. To prove this, we reveal an underlying structure of the set of extremal points.

Given an undirected graph $G$, a collection $\{(s_1,t_1), \dots, (s_{k},t_{k})\}$ of pairs of vertices, and an integer ${{p}}$, the Edge Multicut problem asks if there is a set $S$ of at most ${{p}}$ edges such that the removal of $S$ disconnects every $s_i$ from the corresponding $t_i$. Vertex Multicut is the analogous problem where $S$ is a set of at most ${{p}}$ vertices. Our main result is that both problems can be solved in time $2^{O({{p}}^3)}\cdot n^{O(1)}$, i.e., fixed-parameter tractable parameterized by the size ${{p}}$ of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form $f({{p}})\cdot n^{O(1)}$ exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.

We present a method for reducing the treewidth of a graph while preserving all of its minimal s - t separators up to a certain fixed size k . This technique allows us to solve s - t Cut and Multicut problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set or induce a connected graph) in linear time for every fixed number k of removed vertices. Our results have applications for problems that are not directly defined by separators, but the known solution methods depend on some variant of separation. For example, we can solve similarly restricted generalizations of Bipartization (delete at most k vertices from G to make it bipartite) in almost linear time for every fixed number k of removed vertices. These results answer a number of open questions in the area of parameterized complexity. Furthermore, our technique turns out to be relevant for ( H , C , K )- and ( H , C ,≤K)-coloring problems as well, which are cardinality constrained variants of the classical H -coloring problem. We make progress in the classification of the parameterized complexity of these problems by identifying new cases that can be solved in almost linear time for every fixed cardinality bound.

Given an undirected graph $G$, a collection {(s1,t1), ..., (sl,tl)} of pairs of vertices, and an integer p, the Edge Multicut problem ask if there is a set S of at most p edges such that the removal of S disconnects every si from the corresponding ti. Vertex Multicut is the analogous problem where S is a set of at most p vertices. Our main result is that both problems can be solved in time 2O(p3) ⋅ nO(1), i.e., fixed-parameter tractable parameterized by the size p of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form f(p) ⋅ nO(1) exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.

In many combinatorial problems one may need to model the diversity or similarity of assignments in a solution. For example, one may wish to maximise or minimise the number of distinct values in a solution. To formulate problems of this type, we can use soft variants of the well known AllDifferent and AllEqual constraints. We present a taxonomy of six soft global constraints, generated by combining the two latter ones and the two standard cost functions, which are either maximised or minimised. We characterise the complexity of achieving arc and bounds consistency on these constraints, resolving those cases for which NP-hardness was neither proven nor disproven. In particular, we explore in depth the constraint ensuring that at least k pairs of variables have a common value. We show that achieving arc consistency is NP-hard, however achieving bounds consistency can be done in polynomial time through dynamic programming. Moreover, we show that the maximum number of pairs of equal variables can be approximated by a factor 1/2 with a linear time greedy algorithm. Finally, we provide a fixed parameter tractable algorithm with respect to the number of values appearing in more than two distinct domains. Interestingly, this taxonomy shows that enforcing equality is harder than enforcing difference.

We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These results answer a number of open questions in the area of parameterized complexity.

The (parameterized) feedback vertex set problem on directed graphs, which we refer to as the dfvs problem, is defined as follows: given a directed graph G and a parameter k, either construct a feedback vertex set of at most k vertices in G or report that no such set exists. Whether or not the dfvs problem is fixed-parameter tractable has been a well-known open problem in parameterized computation and complexity, i.e., whether the problem can be solved in time f(k)nO(1) for some function f. In this paper we develop new algorithmic techniques that result in an algorithm with running time 4k k! nO(1) for the dfvs problem, thus showing that this problem is fixed-parameter tractable.

The (parameterized) FEEDBACK VERTEX SET problem on directed graphs (i.e., the DFVS problem) is defined as follows: given a directed graph G and a parameter k , either construct a feedback vertex set of at most k vertices in G or report that no such a set exists. It has been a well-known open problem in parameterized computation and complexity whether the DFVS problem is fixed-parameter tractable, that is, whether the problem can be solved in time f ( k ) n O (1) for some function f . In this article, we develop new algorithmic techniques that result in an algorithm with running time 4 k k ! n O (1) for the DFVS problem. Therefore, we resolve this open problem.