List of open questions

This page is a collection of open problems in theoretical computer science. I have not investigated all of them thoroughly, but I find them interesting. It also features a list of other lists of open problems.

Some problems are very precisely formulated, others are fuzzier. The categories are here for convenience but they are mostly random.

Some of these problems are existing conjectures, though I avoided those that everyone should know, like P vs NP. For problems which are well-known conjectures with existing descriptions that are better than what I could write, I have a dedicated category. Other problems are open problems left as future work in publications that I found interesting. Yet other problems come from my research: however I usually do not list problems that I am working on right now, because the phrasing of the problem (or my understanding of possible solutions) could change too quickly for me to keep this page in sync. Also, some of my questions on TCS.SE may not be immediately reflected here, as I first wait to see whether I get an answer.

For more information about directions for new research (featuring questions that are less precise but more related to my interests), you can look at my internship and PhD offers. If you are a student interested in working with me, not all problems on that page are a good choice: the problems in this list on which I believe I could reasonably supervise someone are marked with an (*).

If you know the answer to a problem, or if you have new information about it, I would be very interested to know! You can write me at a3nm<REMOVETHIS>@a3nm.net.

This document is likely to contains errors of various kinds, and I make no promises about its correctness. Please report any mistakes to the address above.

Posets¶

Complexity of counting antichains in restricted poset classes¶

With Yael Amsterdamer and Tova Milo, we worked on the problem of learning monotone predicates on lattices via crowd queries. We used the result that it is #P-hard to count the number of antichains in a poset¹. However, our results could be strengthened if we knew that hardness also held for distributive lattices. Is it also #P-hard to count antichains in distributive lattices?

More generally, the question is: on which classes of posets is it #P-hard to count antichains?

• TCS.SE question on distributive lattices

Tradeoffs between computational and oracle complexity to learn monotone predicates on posets¶

Our work about learning monotone predicates on lattices via crowd queries shows that (under some formulations of the problem) it is computationally intractable to do so in a way that minimizes the oracle complexity (number of oracle queries). However, we were unable to analyse the oracle performance of non-optimal strategies which are computationally inexpensive.

Formally, the task is the following: we are given a poset $(V,<)$ and we wish to learn exactly a Boolean predicate $P:V\mapsto \{0,1\}$ which is monotone: if $P\left(x\right)=1$ and $x<y$ then $P\left(y\right)=1$. A simple algorithm is to pick (uniformly at random) an element $x$ such that $P\left(x\right)$ is unknown, evaluate $P\left(x\right)$ with the oracle, integrate the consequences of the answer (set $P\left(y\right)=0$ for all $y<x$ if $P\left(x\right)=0$, set $P\left(y\right)=1$ for all $y>x$ if $P\left(x\right)=1$), and repeat while there are unclassified element. Are there posets where the performance of this strategy (expected number of oracle queries) is significantly worse than the (computationally intractable) optimal strategy?

More generally, are there learning algorithms for this task which are computationally tractable and yet have near-optimal oracle complexity?

• Related TCS.SE question
• Another related TCS.SE question

Complexity of finding linear extensions of a labeled poset in a regular language (*)¶

Our work on order-incomplete data studies labeled posets, which consist of a poset $(P,<)$ and a function $\mu$ from $P$ to some finite alphabet $\Sigma$. The label of a linear extension $x_1,\dots ,x_n$ of $(P,<,\mu )$ is the word $\mu \left(x_1\right)\cdots \mu \left(x_n\right)$. A simple question is whether we can efficiently determine, given a labeled poset $(P,<,\mu )$ and a word $w$ in ${\Sigma }^{\ast }$, whether $(P,<,\mu )$ has a linear extension of label $w$. Our work shows that this problem is hard even for comparatively simple $P$, and shows classes of labeled posets where it is tractable. It also studies a generalization of this question where you do not consider just the free monoid ${\Sigma }^{\ast }$ on $\Sigma$, but an arbitrary monoid structure: given a monoid element $w$ and a labeled poset, we ask whether there is a linear extension whose label evaluates to $w$ according to the monoid law.

Of course, another variant of this problem is to consider a language $L$ on $\Sigma$, for instance a regular language, and ask whether the labeled poset has a linear extension whose label is in $L$. The more general question is: for which regular languages is this class tractable? Could one show a dichotomy result separating tractable and intractable languages?

For instance, with the alphabet $\Sigma =\{a,b\}$ and language $L=(ab{)}^{\ast }$, I do not know whether it is tractable, given an input poset $(P,<,\mu )$, to test whether it has a linear extension where we alternate between elements labeled $a$ and elements labeled $b$.

• Our paper about the problem, which settles various special cases
• Page keeping track of the remaining open problems from the paper
• TCS.SE question about the case where the language follows the law of a finite group
• TCS.SE question about the variant of finding the lexicographically minimal topological sort
• TCS.SE question about hardness of a related problem
• TCS.SE question about hardness of a related problem on restricted poset classes

A related question is to characterize the complexity of enumerating linear extensions of labeled posets: the problem can be done in constant amortized delay for classical posets³, but I am not aware of analogous results for labeled posets.

• TCS.SE question about this

Representing the result of duplicate consolidation in labeled posets¶

With M. Lamine Ba, Daniel Deutch and Pierre Senellart, we worked on how to represent and query order-incomplete data. In this context, we studied labeled posets (defined as above) and study the question of how to consolidate duplicates in a labeled poset. By this, we mean that we want to compute a labeled poset where the element labels are unique (all elements with the same label are collapsed to the same element), and the remaining order relations between the collapsed elements are sensible.

However, if you see a labeled poset as a way to represent a set of possible orders (its linear extensions), and if you want the duplicate removal operation to act consistently when looking at each linear extension (i.e., the linear extensions of the duplicate consolidation should be the result of removing duplicates in the linear extensions of the labeled posets), then it is not clear at all how to proceed. In fact, the result of duplicate consolidation may even not be representable as a labeled poset.

Is there a formalism that can represent the result of duplicate consolidation on labeled posets?

Testing whether a set of words can be the set of linear extensions of a labeled poset¶

Define labeled posets as in the previous section. Consider a sequence $S$ of words given as input. A labeled poset $(P,<,\mu )$ represents $S$ if $S$ is exactly the set of labels that can be achieved by the linear extensions of the poset. Of course, a sequence $S$ cannot be thus represented unless all its sequences are built using the same multiset of elements, which should be the image of $\mu$ (seen as a multiset). However, if $S$ respects this condition, it does not seem easy to determine whether it can be represented or not.

What is the complexity of determining, given a set of sequences, whether it can be represented by a labeled poset in this sense?

Stable interpolation on partial orders¶

In our work with Yael Amsterdamer, Tova Milo, and Pierre Senellart, we study an interpolation scheme on partial orders, defined as the center of mass of the convex polytope defined by the order constraints. As it turns out, however, the scheme is not stable: if we fix some variables to their interpolation result, the interpolation of other variables may change.

Is there a principled stable interpolation scheme on posets? Is it unique?

• More general TCS.SE question

Representing bounded treewidth partial orders¶

In our work with Yael Amsterdamer, Tova Milo, and Pierre Senellart, we consider partial orders whose Hasse diagram (or its reverse) is a directed tree. We do not know whether our study would extend to partial orders whose Hasse diagram has bounded treewidth.

Is there a structure on the set of linear extensions of a poset whose Hasse diagram has bounded treewidth? Alternatively, is there a structure on the convex polytope defined by such order constraints?

• Related paper which shows that it is PTIME to count the number of linear extensions of posets whose Hasse diagram has bounded treewidth.

A related question: are there languages for which constrained topological sorting is tractable on partial orders whose Hasse diagram is a tree, or has bounded treewidth, but is hard on arbitrary DAGs?

Smallest posets with prescribed number of linear extensions¶

For all $n\in N$, what is the minimal number of elements of a poset with exactly $n$ linear extensions, if one exists? What is the asymptotic growth of this function?

• Math.SE question

The analogous question for antichains has been studied⁴, with posets of size logarithmic in the desired number of antichains. However, the argument is much simpler, because the posets can be easily constructed from smaller posets. By contrast, the number of linear extensions of a poset seems hard to determine from elementary "constituent parts".

Graphs¶

Detour problem¶

Given a directed graph $G$, a source vertex $s$, and a sink vertex $t$ reachable from $s$, we want to know if there is a simple directed path from $s$ to $t$ whose length is greater than that of the shortest path from $s$ to $t$. Is this problem in polynomial time?

• Last seen open: 2023⁵

A seemingly related question is that of simple paths on DAGs with backward edges. Consider an input DAG $G$, two vertices $s$ and $t$, and additional back edges such that whenever $(u,v)$ is an additional edge then $u$ is reachable from $v$ in $G$. Is it NP-hard to determine whether there is a simple path from $s$ to $t$ that uses at least one additional edge?

• TCS.SE question

3-coloring graphs of diameter 2¶

An undirected graph has diameter 2 if, for every pair of vertices $u\ne v$, there is a path of length at most 2 connecting $u$ and $v$ (i.e., with at most one intermediate vertex). A 3-coloring of a graph is a function mapping each vertex to a value in $\{1,2,3\}$ such that no two adjacent vertices are mapped to the same color.

Given a graph of diameter 2, can we decide in polynomial time whether it admits a 3-coloring?

• Last seen open: 2024⁶

FPRAS for the probability of obtaining a cyclic subgraph of a directed graph¶

We are given a directed graph $G$ whose edges are annotated with independent probabilities of existence, and we want to estimate the probability of obtaining a subgraph of $G$ which contains a directed cycle. Is there an FPRAS for this task?

• CStheory question (2023)
• Paper leaving the problem open (to appear in 2024)

Simple paths of fixed modulo length on undirected graphs (*)¶

Given an undirected graph and two nodes, can one decide in polynomial time whether there is a simple path of length 0 modulo 3 between the two nodes?

• Last seen open: 2022⁷.

The problem without the "simple" requirement is clearly in PTIME, and the same problem on a directed graph is NP-hard by a reduction from the 2 disjoint paths problem. The question is also open for paths of length $p$ modulo $q$ for other values of $p$ and $q$. It can be determined in PTIME if all simple paths between two vertices of an undirected graphs are of length p modulo q, solving the problem for $q=2$⁸.

Up to subdividing each edge by 2 and connecting the source and target nodes by an edge, we can reduce to the problem of deciding if an undirected graph has a simple cycle of length $2p+1$ mod $2q$. This question is also open: a related comment is at the end of these slides (2015). A sufficient condition for tractability was given in 2004⁹, but it does not cover the right cases, so the problem remains open.

I have written (in 2023) a more detailed writeup on the related work around this problem.

Number of hunters to catch a rabbit (*)¶

The hunters and rabbit problem is a pursuit-evasion game played on a undirected graph. A strategy for $k$ hunters is a sequence $s_1,\dots ,s_n$ of subsets of $k$ vertices. A strategy is winning if, for every walk $v_1,\dots ,v_n$ in the graph (not necessarily simple), there is $i$ such that $v_i\in s_i$. Intuitively, the evader is walking on the graph (it has to move at each turn by following exactly one edge) and must avoid the $k$ vertices that the pursuers examine at each time step.

The evasion number of a graph $G$ is the smallest $k$ for which there is a winning strategy with $k$ hunters. What is the complexity, given an undirected graph, of computing its evasion number? e.g., it is the case that, for any constant $k$, we can recognize the graphs of evasion number $k$ in polynomial time?

This relates to the question of whether graphs with evasion number $\ge k$ can be somehow characterized, similarly to the links between treewidth and pursuit-evasion via havens. It also relates to the question of how the maximal length of a strategy can be bounded as a function of the graph size and of $k$.

• TCS.SE question
• Bruteforce implementation
• Paper which characterizes the graphs with evasion number $k=1$ (they are the unions of lobster graphs, and can be recognized in linear time), and determines explicit strategies for them. In this paper the pursuer is called a prince and the evader is called a princess. See also this Reddit discussion, where the pursuer is a vampire hunter and the evader is a vampire.
• Some recent papers on the topic:
  • How to Hunt an Invisible Rabbit on a Graph
  • Catching a Mouse on a Tree, where the pursuers are called cats and the evader mouse
  • Hunting Rabbits on the Hypercube, which follows the hunter/rabbit terminology
  • Recontamination Helps a Lot to Hunt a Rabbit.

Computing the treewidth of planar graphs¶

Treewidth measures how much an undirected graph is close to a tree. It is known that, for any fixed $k\in N$, we can check in linear time in an input graph $G$ whether its treewidth is $\le k$; but that, when both $k$ and $G$ are given as input, it is NP-hard to determine whether $G$ has treewidth $\le k$.

Is this last statement still true if $G$ is planar, or can the treewidth of a planar graph $G$ be computed in PTIME?

• TCS.SE question

Computing cliquewidth¶

The parameterized cliquewidth computation problem for $k\in N$ asks, given an input graph $G$, whether $G$ has cliquewidth $\le k$. Is this problem in PTIME for any fixed $k$? Is there $k\in N$ such that the problem is NP-hard?

Membership in PTIME was recently shown¹⁷ for $k\le 3$, but the problem is open for larger $k$. In particular, we do not know whether the problem is in FPT. Membership in FPT is known for some restricted classes of graphs of unbounded cliquewidth¹⁸, and membership in cubic FPT is known for the related parameter of rankwidth¹⁹.

• Last seen open: 2012¹⁷.

Optimal bound on the size of a grid minor¶

The grid minor theorem²⁰ of Robertson and Seymour shows that, if a family of graphs has unbounded treewidth, then one can find arbitrary large grid graphs as minors of the family. Specifically, the result can be stated as follows²¹: there exists a function $f:N_{>0}\to N_{>0}$ such that, for every $g\in N_{>0}$, every graph of treewidth $\ge g$ has the $(g\times g)$-grid as a minor.

The best known upper bound²¹ on $f$ is $\tilde{O}\left(g^{19}\right)$, where the $\tilde{O}$ notation neglects polylogarithmic factors. The best known lower bound²² is $\Omega \left(g^2\log g\right)$.

What is the correct bound on the function $f$?

• Last seen open: 2016²¹. See²¹ for discussion of conjectured bounds.

Extracting a polynomial grid minor in PTIME¶

Continuing on the grid minor theorem from the previous entry, the following result is known²³: there is $c\in N$ such that for any $n\in N$, for any graph $G$ of treewidth $\ge n^c$, one can find the $n\times n$ grid as a minor of $G$. This work shows how the minor can be found in randomized polynomial time.

Is it possible to extract the minor in deterministic PTIME?

• Last seen open: 2015²⁴.

Monadic second-order logic with cardinality predicates¶

We extend monadic second-order logic (MSO) over graphs with constructs to check the equality of the cardinalities of second-order variables, and check that their cardinalities are in fixed recursive sets. We fix a formula $\Phi$ in this logic and a treewidth bound $k\in N$. Is it PTIME in an input graph $G$ of treewidth $\le k$ to check whether it satisfies $\Phi$?

Courcelle's theorem states that this is true (and in linear time) for normal MSO without the extension.

• The question on Open Problem Garden

Graph reachability labellings with total orders¶

A labeling of a directed acyclic graph (DAG) $G=(V,E)$ is a function $\mu$ from $V$ to some set $\Sigma$ of labels such that the labels of a pair of vertices suffice to test reachability. Formally, there is a decoding function $f:{\Sigma }^2\to \{0,1\}$ independent of $G$ such that for any two vertices $u,v\in V$, we have $f\left(\mu \right(u),\mu (v\left)\right)=1$ iff $v$ is reachable from $u$ in $G$.

I am interested in labeling schemes where $\Sigma$ is $N^d$ for a certain $d$, and where for simplicity we assume that $\mu$ cannot use the same number twice: there are no $u\ne v$ in $V$ such that, letting $\ell =\mu \left(u\right)$ and ${\ell }^{\prime }=\mu \left(v\right)$, we have ${\ell }_i={\ell }_j^{\prime }$ for some $1\le i<j\le d$. Further, the decoding function $f$ can only use the labels to do comparisons on their components, i.e., $f$, when applied on $(\ell ,{\ell }^{\prime })$ can only see whether ${\ell }_i<{\ell }_j^{\prime }$ for all $1\le i,j\le d$. Given $d\in N$ and a choice of decoding function $f$, the labelable graphs of $f$ are those for which there is a reachability labeling scheme for $f$.

These definitions generalize several known notions:

• The case $d=1$ is uninteresting: there is only a single possible scheme $f$, and the labelable graphs are the directed path graphs.

• For $d=2$, considering the decoding function $f(\ell ,{\ell }^{\prime })$ that checks whether ${\ell }_2<{\ell }_1^{\prime }$, the labelable graphs are those that represent interval orders

• For $d=2$, considering the decoding function $f(\ell ,{\ell }^{\prime })$ which is true iff ${\ell }_1<{\ell }_1^{\prime }$ and ${\ell }_2<{\ell }_2^{\prime }$, the labelable graphs are those that represent posets with order dimension at most two. More generally, for arbitrary $d\in N$, for the function that takes the AND of the pointwise comparability relations, the labelable graphs are those that represent a partial order with dimension $\le d$.

For other values of $d$ and decoding functions, how can we characterize the labelable graphs? In particular, for a given value of $d$, are some decoding functions more expressive than others? (For $d=2$ and the two decoding functions that I presented, interval orders and orders of dimension $\le 2$ are incomparable.) Further, is there $d\in N$ and some decoding function such that any graph has a reachability labeling with $N^d$? (This sounds extremely unlikely but I'm not sure of how to prove it.)

• Preliminary notes about these problems
• It appears that the notion of labeling schemes with decoding function presented here, up to some minor differences, has been introduced in this paper³¹ (see conclusion) under the name local presentation. In their terminology, a local presentation of a DAG is a function mapping each vertex to a $d$-tuple of integers, with the decoding function being a Boolean function of equalities and inequalities on the tuple components: this is exactly the definition above except that the same number can be used multiple times and we can test for equality. The notion does not seem to have been studied again since that paper, though there have been studies of the related notion of Boolean dimension: this is the case where we can only do comparisons between ${\ell }_i$ and ${\ell }_i^{\prime }$, i.e., between the same components of the labels. In particular I didn't find an example of a poset family where the size $d$ of local presentations was unbounded.

Boolean dimension of planar posets¶

Let $G=(V,E)$ be a directed acyclic graph (DAG). A Boolean realizer of $G$ is intuitively a way to label each vertex of $G$ with integers, such that reachability in $G$ can be determined only by looking at some Boolean function over pairwise comparisons of the vertex labels. Formally, a Boolean realizer of $G$ of dimension $d\in N$ consists of a Boolean function $\varphi$ on $d$ variables, and of $d$ labellings ${\ell }_1,\dots ,{\ell }_d$, each of which is an injective function from $V$ to $N$: we require that for any two vertices $u,v\in V$, letting $x_i$ for all $1\le i\le d$ be $1$ if ${\ell }_i\left(u\right)<{\ell }_i\left(v\right)$ and $0$ otherwise, we have $\varphi (x_1,\dots ,x_d)=1$ iff $v$ is reachable from $u$ in $G$. The Boolean dimension of $G$ is then the smallest $d$ for which $G$ has a Boolean realizer of dimension $d$.

Is the Boolean dimension of planar DAGs bounded? In other words, is there a constant $k\in N$ such that, whenever $G$ is planar (i.e., it can be drawn in a way such that no two edges cross), then the dimension of $G$ is no greater than $k$?

• Posed in: 1989 (cited in³²)
• Last seen open: 2018³²

Complexity of computing a simplicial decomposition¶

A simplicial decomposition of a graph $G$ is a tree decomposition such that, for any two adjacent bags $b$ and $b^{\prime }$ whose set of vertices is respectively $X$ and $X^{\prime }$, the subgraph induced by $G$ on $X\cap X^{\prime }$ is a clique. The width of the decomposition is the size of the largest bag minus one, as usual for treewidth. The simplicial width of $G$ is the smallest possible width of a simplicial decomposition. What is the complexity, given a graph $G$, of computing its simplicial width and a simplicial decomposition? One can ask the question when allowing arbitrary $G$, or when assuming that the simplicial width of the input graph is bounded by a constant.

Note that there are known results³³ on the complexity of computing a clique minimal separator decomposition, i.e., a simplicial decomposition where we minimize the size of the cliques, not of the bags.

• Paper of mine which uses simplicial decompositions.

Covering an undirected graph with cycles of length at least 5¶

What is the complexity of determining if an input undirected graph can be covered by cycles, each of which have length at least 5? The problem is known to be PTIME for a length constraint of "at least 3" or "at least 4", and NP-hard for a length constraint of "at least $k$" for all $k\ge 6$.

• Source

Databases and logic¶

Oracle complexity of skyline queries¶

Consider a set of $d$-dimensional vectors $V=v^1,\dots ,v^n$ of numbers (or indeed any totally ordered set). Let us assume for simplicity that all the $v_l^i$ are distinct for $1\le i\le n$ and $1\le l\le d$. In this context, we say that $v^i$ dominates $v^j$ if $v_l^i\ge v_l^j$ for all $1\le l\le d$. The skyline (or Pareto frontier) of $V$ is the set of maximal vectors for the domination relation.

Assume that the only way you can access the vectors of $V$ is by atomic comparisons, i.e., you can evaluate whether $v_l^i<v_m^j$ for any $1\le i,j\le n$, $1\le l,m\le d$. What are bounds on the minimal number of comparisons required to determine the skyline? Such bounds can be stated as a function of $k$ and $n$, or as a function of the output size (the actual skyline).

Groz and Milo¹⁰ have studied this problem when the comparisons are additionally noisy, but good bounds for $d>3$ are not yet known, even without noise.

Constraint classes where separability is decidable¶

Consider a set $\Sigma$ of tuple-generating dependencies (TGDs) and a set $\Phi$ of equality-generating dependencies (EGDs). We say that a Boolean conjunctive query (CQ) $Q$ is entailed by a relational database instance $I$ and by $\Sigma \wedge \Phi$ if, for every superinstance $I^{\prime }\supseteq I$ such that $I^{\prime }$ satisfies $\Sigma \wedge \Phi$, it is the case that $I^{\prime }$ satisfies $Q$. Intuitively, $Q$ is implied by the instance $I$ and the constraints $\Sigma \wedge \Phi$ under open-world semantics: $Q$ is true on all superinstances of $I$ that satisfy the constraints $\Sigma \wedge \Phi$.

We call $\Sigma$ and $\Phi$ separable if, for any Boolean CQ $Q$ and instance $I$ that satisfies $\Phi$, the following equivalence holds: $Q$ is entailed by $I$ and $\Sigma \wedge \Phi$ iff $Q$ is entailed by $I$ and $\Sigma$. In other words, the equality-generating dependencies $\Phi$ can be checked separately on $I$, and have no impact afterwards in terms of entailment.

For general TGDs and EGDs, the problem is undecidable¹¹, but this is not so surprising as reasoning with TGDs by themselves is also undecidable if arbitrary TGDs are allowed. Are there less expressive languages for which separability is decidable? One could think, e.g., of inclusion dependencies and functional dependencies, maybe with some restrictions.

Open-world query answering with linear rules and transitivity assertions¶

A linear rule is a tuple-generating dependency (TGD) with exactly one atom in the body and one atom in the head. A transitivity assertion on an arity-two relation $R$ is a TGD of the form $\forall xyzR(x,y)\wedge R(y,z)\Rightarrow R(x,z)$.

It is decidable²⁵ whether an instance $I$ and constraints $\Sigma$ of linear rules and transitivity assertions entail a CQ $Q$, in the sense of the previous problem, but under some restrictions (all relations have arity at most two, or $Q$ consists of a single atom, or an additional condition holds). Does decidability hold in the general case of arbitrary CQ and arbitrary arity signatures for linear rules and transitivity assertions?

Decidable unary language with number restrictions¶

With Michael Benedikt we introduced a language formed of expressive constraints on an arity-two signature (including number restrictions, namely counting quantifiers) and tuple-generating dependencies on arbitrary arity predicates, also supporting functional dependencies of a restricted kind on such predicates. We showed that it was decidable to determine (in the sense above) whether a query is entailed by an instance and such constraints, which we call the open-world query answering (OWQA) problem.

This raises the question of whether a more expressive and more uniform such language could be designed. It should also have decidable entailment, and should also feature (1) arbitrary arity constraints, (2) number restrictions such as functional dependencies, and (3) expressive logical operators such as disjunction. Can such a language be designed? Relevant results include the following (beyond the ones shown in the paper mentioned above):

• OWQA is decidable for the two-variable guarded fragment of first-order logic with counting quantifiers²⁶. This covers (2) and (3).
• OWQA is decidable for the guarded fragment of first-order logic²⁷: this covers (1) and (3).
• OWQA is decidable with functional dependencies and unary functional dependencies, thanks to the fact that they satisfy the non-conflicting condition²⁸. The same holds for other classes of tuple-generating dependencies for which OWQA is decidable (e.g., guarded tuple dependencies) and functional dependencies. This covers (1) and (2).
• OWQA is not decidable for inclusion dependencies and functional dependencies in general, because their implication problem is undecidable²⁹, and it reduces³⁰ to OWQA. This means we cannot have (1) and (2) without restrictions.

A general idea would be to design a language that generalizes frontier-one TGDs to have disjunction and some kind of "non-conflicting" counting quantification, and establish decidability.

Following this paper, another natural direction would be to study finite model reasoning for such a language. However, one should first show the decidability of the finite implication problem for it: decide whether a set of constraints of the language implies other constraints. Yet, as far as I know, the only decidability result for finite implication on an arbitrary-arity language that features number restrictions only covers⁴⁰ unary inclusion dependencies and functional dependencies. Can finite implication be decided for a more expressive language of this form? E.g., in the spirit of existing works⁴¹ but for arbitrary arity constraints.

Decidability of finite query answering with path-functional dependencies and two-variable guarded constraints¶

This question uses the definition of OWQA from the previous question. It was recently shown⁴² that the finite satisfiability problem is decidable for the two-variable guarded fragment of first-order logic with counting quantifiers (GC²) to which one adds path-functional dependencies. Is the same true of the finite OWQA problem? This is already known if there are no path dependencies²⁶.

If this is true, it would imply an independent proof of the result of this paper when assuming that all functional dependencies are unary. Indeed, unary inclusion dependencies and functional dependencies on arbitrary signatures can clearly be equivalently translated to GC² plus path functional dependencies (with paths of length 2). To re-prove this result for arbitrary functional dependencies, one would need some generalization of path functional dependencies (to capture the image of this translation).

Decidability of conjunctive query containment under bag semantics¶

Is conjunctive query containment under bag semantics decidable, and what is its complexity?

• Slides (2013) that define the problem.

Determinacy of path queries by unions of path views¶

For $k\in N$, the path query $q_k$ of length $k$ on a directed graph $G=(V,E)$ returns the set of pairs of nodes $(u,v)\in V^2$ such that there is a path of length $k$ from $u$ to $v$. A union of path queries $q_S$ is defined by a (possibly infinite) set $S$ of integers and returns the sets of pairs of nodes $(u,v)$ such that there is a path from $u$ to $v$ whose length is in $S$.

A set of union of path queries $Q=q_{S_1},\dots ,q_{S_n}$ determines a path query $q_k$ if, for all finite graphs $G$ and $G^{\prime }$, if $q_{S_i}\left(G\right)=q_{S_i}\left(G^{\prime }\right)$ for all $1\le i\le n$, then $q_k\left(G\right)=q_k\left(G^{\prime }\right)$. Under mild assumptions on the representation of infinite sets in union of path queries, the determinacy problem was shown⁴⁴ to be decidable but only for path queries $q_k$ where $k$ is larger than some function of $Q$. Is it decidable to determine whether a path query is determined by a set of union of path queries, without this restriction?

Another question is whether this result extends to more general query languages. For instance, is it decidable to determine whether a union of path queries is determined by a set of union of path queries?

A natural further generalization of this problem is going from paths of a fixed length to paths labeled by some language, when edges are labeled by letters of some alphabet. Formally, we define a regular path query $q_L$ as a query on edge-labeled graphs that returns the pairs of vertices connected by a path in $L$, where $L$ is a regular language over the alphabet of edge labels. In this context, however, it was shown that it was undecidable whether a regular path query was determined by a set of regular path queries⁴⁵, and it is even undecidable whether using only finite regular languages⁴⁶ (or, equivalently, union of labeled path queries, i.e., unions of queries returning all pairs of vertices separated by a path labeled by some finite word). So with these generalisations of the above problem being undecidable, it is not clear whether we should expect decidability for (unlabeled) path queries, or unions thereof.

Thanks to Nadime Francis and to Bartosz Bednarczyk for helping me to prepare this entry.

Do tractable queries on probabilistic instances have tractable lineages? (*)¶

A tuple-independent database (TID) is a probabilistic database consisting of a relational database $I$ where each tuple is given a probability in $[0,1]$. The semantics is a probability distribution on subsets of $I$ (the possible worlds), obtained by considering that each tuple is either kept or removed with the indicated probability, independently across tuples.

A Boolean union of conjunctive queries (UCQ) is a disjunction of conjunctive queries with no free variables. The probability evaluation problem for a fixed Boolean UCQ $q$ asks, given a TID $I$, what is the probability that $I$ satisfies $q$, meaning, what is the total probability mass of possible worlds of $I$ that satisfy $q$. A dichotomy result is known⁴⁷: Boolean UCQs are partitioned between those for which the probability evaluation problem can be solved in polynomial time, and those where it is #P-hard.

The lineage of a Boolean query $q$ on a TID instance $I$ is a Boolean formula whose variables are the facts of $I$, such that a valuation makes the circuit evaluate to true iff the corresponding possible world (defined by keeping exactly the facts set to true) satisfies $q$. One way to show that a Boolean UCQ is tractable is to show that, on any instance, one can represent its lineage in a form that allows for tractable probability evaluation.

A d-DNNF${}^{\neg }$ is a Boolean circuit (with AND, OR, NOT gates, and input gates) such that every AND gate is on disjoint set of variables (meaning, there is no input gate reachable from two distinct children of an AND gate), and every OR gate is exclusive (meaning, there is no valuation of the input gates that makes two distinct children of an OR gate evaluate to true). A Boolean UCQ has polynomial-size d-DNNF${}^{\neg }$ if there is a constant $c\in N$ such that, for any TID instance $I$, there is a d-DNNF${}^{\neg }$ of size $O\left({\left|I\right|}^c\right)$ that expresses the lineage of $q$ on $I$.

It is known⁴⁸ that many Boolean UCQs for which probabilistic query evaluation is in PTIME have polynomial-size d-DNNF${}^{\neg }$, but the converse is open. Is there a Boolean UCQ for which probabilistic query evaluation is in PTIME, but that has no polynomial-size d-DNNF${}^{\neg }$? In particular, is this the case of the conjectured⁴⁸ counterexample $Q_9$? If this can be shown, is it possible to design a generalization of d-DNNF${}^{\neg }$ that still enjoys probabilistic query evaluation, and is such that any Boolean UCQ with PTIME probabilistic query evaluation has a polynomial-size lineage in this generalization?

Update: the most recent work in this area is this paper by Mikaël Monet

Does bounded derivation depth imply finite controllability?¶

We talk of a Boolean conjunctive query $Q$ being entailed by an instance $I$ and set $\Sigma$ of tuple-generating dependencies (TGDs) if for any instance $I^{\prime }\supseteq I$ such that $I^{\prime }\models \Sigma$, we have $I^{\prime }\models Q$.

The set $\Sigma$ of tuple-generating dependencies (TGDs) has bounded derivation depth if, for any conjunctive query $Q$, there exists a union of conjunctive queries $Q^{\prime }$ such that, for any relational instance $I$, the following equivalence holds: $Q$ is entailed by $I$ and $\Sigma$ iff $I\models Q^{\prime }$.

The set $\Sigma$ of TGDs is finitely controllable iff for any instance $I$ and Boolean conjunctive query $Q$, the following equivalence holds: $Q$ is entailed by $I$ and $\Sigma$ iff $Q$ is entailed by $I$ and $\Sigma$ over finite models (impose that $I^{\prime }$ is finite in the definition above).

Is it the case that if a set of TGDs has bounded derivation depth then it is finitely controllable? In the work where this conjecture was posed⁴⁹, it was solved for signatures of arity two, but the general question remains open.

What is the complexity of testing if a query is safe?¶

This question refers to the dichotomy⁴⁷ on the Boolean UCQs for which the probability evaluation problem is in PTIME: see this question for background. The queries which are tractable according to this dichotomy are safe.

What is the complexity, given a Boolean UCQ, to determine whether it is safe?

The best known algorithm for this is super-exponential¹⁵.

• Last seen open: 2011¹⁵

Complexity of query evaluation parameterized by treewidth¶

The query evaluation problem asks, given a Boolean conjunctive query $Q$ and a relational database $I$, whether $Q$ holds on $I$. The treewidth of $I$ is the treewidth of its Gaifman graph, and the treewidth of $Q$ is that of its canonical instance (i.e., we just see the query as a database on its variables). What is the parameterized complexity of the query evaluation problem when parameterized by the treewidth of $I$ and of $Q$? (In other words, the parameter of the problem is an upper bound on the treewidth of both $I$ and $Q$.)

• CStheory question where the problem is phrased in terms of graph homomorphisms (query evaluation can be understood as deciding the existence of a homomorphism between labeled hypergraphs). Also includes pointers to related work.

How can one strengthen lower bounds for probabilistic query evaluation on unbounded-treewidth families? (*)¶

In this paper with Pierre Bourhis and Pierre Senellart, we showed (Theorem 4.2) that there is a query for which the probabilistic query evaluation problem (see this question for the definition) is intractable on any unbounded-treewidth instance family. However, the lower bound of this result has some limitations, and I do not know whether they can be lifted:

• Does the result generalize to arbitrary arity signatures rather than arity-2 signatures?
• Can the query be in a weaker language than MSO? For instance, can it be a union of conjunctive queries with inequalities (${\text{UCQ}}^{\ne }$)?
• Does the result hold even if we are not completely free to choose the probability valuation of the input instance?
• Is it possible to use PTIME reductions rather than RP reductions? This is asked separately as this question.

Lower bounds on lineage sizes¶

In the same paper as in the previous question, we showed (in Lemma 8.2) that, for any graph signature, there is a UCQ with inequalities $Q$ such that, given any instance $I$, the width of any OBDD representing the lineage of $Q$ on $I$ (see this question for the definition) is bounded by an exponential function of the treewidth of $I$: specifically, there is a constant $c\in N_{>0}$ such that it is in $\Omega \left(2^{\left(\text{width}\right(I){)}^{1/c}}\right)$.

Can the same result be shown for other lineage representations? In particular, can it be shown for d-DNNFs?

Update: our ICDT'19 paper with Mikaël Monet and Pierre Senellart shows a similar lower bound for the class of d-SDNNF (structured d-DNNF). The question of showing a similar bound for d-DNNF is very challenging and relates to the open problem of separating DNFs in general and d-DNNFs.

Boolean functions and circuits¶

Monotone dualization¶

The prime CNF of a monotone Boolean function over variables $x_1,\dots ,x_n$ is the (unique up to order) expression of the function as a conjunction of disjunctions of the $x_i$ from which no variable occurrence can be removed. The dual of a monotone Boolean function $f$ is the monotone Boolean function mapping $x_1,\dots ,x_n$ to $\neg f(\neg x_1,\dots ,\neg x_n)$. By De Morgan's laws, a Boolean expression for the dual can be obtained by replacing $\wedge$'s by $\vee$'s and vice-versa in the prime CNF of $f$.

The Dual problem asks, given two prime CNFs, whether the functions defined by these CNFs are dual of one another. It is known to be in quasipolynomial time¹⁶. Is the Dual problem in PTIME?

Explicit Boolean functions with supralinear circuits¶

Shannon proved in 1949 with a counting argument that most Boolean functions cannot be represented by a circuit of linear size. However, we do not know yet of any explicit Boolean function for which no linear size circuit exists. Can we construct such a function?

• TCS.SE question
• TCS.SE question about the lowest classes for which a supralinear bound is known

Conciseness gap between formulae and circuits¶

Boolean functions can be represented as circuits or as formulae. Circuits seem much more concise, because they can reuse common subexpressions. Yet the best conciseness gap known is the following: there are Boolean functions that can be represented by linear circuits but for which any formula representation has size at least $n^{3-o\left(1\right)}$ (over circuits with AND, OR, and NOT). Can we do better?

• TCS.SE question

Size bounds on smoothing structured circuit representations¶

A Boolean circuit is structured if there is a fixed full binary tree whose leaves are labeled by the variables (the vtree) and a mapping from the gates of the circuit to the nodes of the tree such that every variable is mapped to the leaf corresponding to itself and the inputs to every gate $g$ are mapped to descendants of the node to which $g$ is mapped. A Boolean circuit is smooth if, intuitively, no variable is omitted, i.e., whenever we take the disjunction of two gates then the set of variables reachable from each gate is the same.

Given a Boolean structured circuit, what is the complexity of computing an equivalent circuit which is structured but still smooth? What about the same question while preserving other desirable circuit properties such as being deterministic?

• Paper with complete definitions and a partial result (Proposition 7.1)

A circuit is decomposable if the inputs to every AND-gate depend on pairwise disjoint sets of variables. What can be said about the same question for smoothing decomposable circuits? There is a partial result (applying only to a certain class of "smoothing-gate algorithms") as Theorem 5.2 in the paper above.

Formal languages¶

Shortest superpermutation¶

An $n$-superpermutation is a word $w$ over $\{1,\dots ,n\}$ such that each permutation of $\{1,\dots ,n\}$ occurs as a subsequence of $w$. What is the length of the shortest $n$-superpermutations as a function of $n$?

• Wikipedia page
• Quanta Magazine article from 2018
• MO.SE question

Languages recognized by polynomial-size DFAs¶

Which languages can be recognized by a (not necessarily uniform) family of deterministic finite automata of polynomial size?

• TCS.SE question

Context-freeness of primitive words¶

A primitive word is a word that cannot be represented as a power of another word. Is it true that, on any alphabet with more than one letter, the set of all primitive words is not context-free?

• There is a book about the question (not available online): P. Domosi, M. Ito, Context-Free Languages and Primitive Words

Words without shuffle squares (*)¶

Fix an alphabet $\Sigma$. We say that a word $w\in {\Sigma }^{\ast }$ is the shuffle of two words $u,v\in {\Sigma }^{\ast }$ if we can obtain $w$ by interleaving $u$ and $v$. A word $w\in {\Sigma }^{\ast }$ is a shuffle square if there is a word $u\in {\Sigma }^{\ast }$ such that we can obtain $w$ as the shuffle of $u$ and $u$. (Note that this implies that, for each letter $a\in \Sigma$, there is an even number of occurrences of $a$ in $w$. While the number of occurrences of each letter in $u$ are uniquely defined from $w$, the order of the letters is not.) We say that a word is shuffle-square-free if it contains no substring which is a shuffle-square.

If the alphabet $\Sigma$ has at least $6$ letters then it is known that there exist infinitely many shuffle-square-free words⁵⁰, following an earlier result⁵¹ on alphabet size $7$. If the alphabet $\Sigma$ has 3 letters or less, then it is known⁵² that such words do not exist: the longest such words on $\Sigma =\{a,b,c\}$ are abcacbacabc, acbabcabacb, bacbcabcbac, bcabacbabca, cabcbacbcab, cbacabcacba, of length 11 each. (I'm adding them to this entry to ensure that people interested in this computation can easily find the page. ;)) The question is open for alphabets of size 4 and 5.

Are there infinitely many shuffle-square-free words on an alphabet of size 4?

• Source code repository which we used to bruteforce the computation of large shuffle-square-free words using a SAT solver. Some documentation is provided as a README. This is joint work with Charles Paperman.

Which regular tree languages can be recognized by a word automaton?¶

Given a tree alphabet $\Sigma$, we define the alphabet $\overline{\Sigma }$ to consist of $\{a\mid a\in \Sigma \}\cup \{\overline{a}\mid a\in \Sigma \}$. Given an unranked tree $T$ on a tree alphabet $\Sigma$, the XML representation of $T$ is the word on $\overline{\Sigma }$ recursively defined as follows: the coding of a leaf labeled $a\in \Sigma$ is $a\overline{a}$, and the coding of an internal node labeled $a\in \Sigma$ with children $n_1,\dots ,n_k$ is $a{c}_1\cdots c_k\overline{a}$ where each $c_i$ is the coding of $n_i$.

Given a tree automaton $A$ on unranked trees on $\Sigma$, it defines a so-called regular tree language $L\left(A\right)$, and we denote by $XML\left(L\right(A\left)\right)$ the word language on $\overline{\Sigma }$ of the XML codings of trees of $L\left(A\right)$. Of course, for all regular tree languages except finite ones, $XML\left(L\right(A\left)\right)$ is not regular as a word language, because a word automaton cannot check if the opening and closing tags (i.e., the $a$'s and $\overline{a}$'s) are properly nested. The question is intuitively to understand the regular tree languages for which matching the opening and closing tags is the only difficulty.

Formally, we say that a word automaton $A$ weakly recognises a tree language $L$ if, given a word $w$ on $\overline{\Sigma }$ which is the XML representation of some tree $T$, then $A$ accepts $w$ iff $T\in L$. (The behavior of $A$ on words of $\overline{\Sigma }$ that do not represent any tree is not specified.)

Given a tree automaton $A$, is it decidable to determine if there exists a word automaton that weakly recognizes the language $XML\left(L\right(A\left)\right)$?

The problem, in the specific case of DTDs (a special case of tree automata), has been shown⁵³ to be equivalent to a variant of the word problem for groups, whose decidability status is open. The status of the general problem is also open.

Thanks to Bartosz Bednarczyk for pointing out this problem to me, and to Charles Paperman for the problem phrasing used here.

Miscellaneous¶

Lower bounds on representations of provenance¶

The Why-provenance⁵⁴ of a Boolean query $q$ in the positive relational algebra on a relational instance $I$ is a Boolean function $\varphi$ defined on the facts of $I$ such that, for any valuation $\nu$ mapping each fact of $I$ to true or false, $\nu \left(\varphi \right)$ is true iff $\{F\in I\mid \nu (F\left)\text{is true}\right\}$ satisfies $q$.

It is known⁵⁴ that, for any such fixed query $q$, its Why-provenance on $I$ can be represented as a Boolean formula of polynomial size in the instance $I$. Are there instance families with known lower bounds on the representation of Why-provenance? In particular, is there a query $q$ and family of relational instances $I_1,\dots ,I_n,\dots$, such that, letting ${\varphi }_i$ for all $i$ be the Why-provenance of $q$ on $I_n$, the size of ${\varphi }_i$ is superlinear in $I_i$, namely, there is no constant $K$ such that, for all $i$, the provenance ${\varphi }_i$ can be written as a Boolean formula of size less than $K\cdot |I|$, where $|I|$ is the number of facts of $I$.

The question generalizes to other representations of provenance, such as provenance circuits⁵⁵, or to provenance expressed in different provenance semirings⁵⁴, such as the universal semiring $N\left[X\right]$ of polynomials in $X$ (standing for the facts of $I$).

Complexity of multi-machine scheduling of jobs with start dates, end dates, and equal duration¶

We have a certain number $m$ of machines, and a number $n$ of jobs. All jobs have the same duration (an integer $p$), and each job has a minimum start date and a maximal end date, both of which are integers. The scheduling problem asks whether there is a way to schedule all $n$ jobs on the $m$ machines. We can phrase it in two variants: the decision variant simply asks whether it is possible, and the computation variant asks us to compute a possible schedule, i.e., a partition of the $n$ jobs into $m$ sequences such that each machine can perform its sequence of $m$ jobs in a way that respects the start date and end dates of all jobs, and the job duration. The problem can equivalently be phrased with jobs of unit duration and start and end dates which are rationals.

Somewhat surprisingly (to me at least), this problem can be solved in PTIME. The best known algorithm⁶⁰ (which additionally optimizes an additional criterion) runs in time $O\left(min\right(1,\frac{p}{m}\left)n^2\right)$. What is the most efficient algorithm for this problem?

For the case $m=1$, a more efficient algorithm is known⁶¹, which runs in $O\left(n\log n\right)$. In this setting, there is a clear lower bound of $\Omega \left(n\log n\right)$ for the computation problem, as the scheduling problem for jobs with disjoint intervals amounts to sorting their bounds; but for the decision problem, this is unclear.

Thanks to the judges of the 2017 ACM-ICPC World Finals for bringing this problem to my attention (see Problem H, "Scenery").

Which convex polytopes have volumes of polynomial bit-length?¶

In this question, all numbers are represented as rationals. Consider a convex polytope described as an intersection of half-spaces, each of which is described as inequalities between a linear function of the coordinates and a constant (e.g., $x_1+\frac{7}{42}{x}_2\le 3$). We assume that the polytope is bounded, i.e., it is not infinite. Given such a representation, we wish to compute the volume of the polytope. It turns out⁶² that this cannot be done in polynomial time (or even in nondeterministic PTIME) because the volume is not always of polynomial length in the input description. Hence the question: For which classes of polytopes is the volume always of polynomial length in the input?

• TCS.SE question

Well-known conjectures¶

• The 1/3-2/3 conjecture: In every non-totally-ordered poset $P$, there are $x$ and $y$ such that $x<y$ in at least 1/3 and at most 2/3 of the linear extensions of $P$.
• The removable pair conjecture: Can you always remove two elements from a poset of $\ge 3$ elements such the order dimension drops by at most 1?
• The union-closed sets conjecture: calling a family of sets union-closed if the union of any sets in the family remains in the family, is it true that any union-closed finite family of finite sets must have an element occurring in at least half the sets of the family? (except the family containing just the empty set)
• The reconstruction conjecture: Given a graph $G$ with $n$ vertices, its deck is the multiset of the $n$ subgraphs obtained, for each vertex, by deleting this vertex and its incident edges. For $n\ge 3$, if two graphs have the same deck (up to isomorphism), are they necessarily isomorphic?
• What is the complexity of matrix multiplication?
• Can integer factorization be done in polynomial time?
• The Zarankiewicz problem: given $m,n,s,t$, how many edges can you put into a bipartite graph between $m$ vertices and $n$ vertices, such that there is no complete bipartite subgraph between $s$ vertices or $t$ vertices?
• The strong Aanderaa–Karp–Rosenberg conjecture
• The Erdős–Gyárfás conjecture: does every 3-regular graph have a simple cycle whose length is a power of two?
• Singmaster's conjecture: is there a constant bounding the maximal number of times that a number different from 1 may appear in Pascal's triangle?
• Tuza's conjecture: is it true that the smallest size of a subset of edges that hits all triangles of a graph is at most two times the largest number of edge-disjoint triangles that can be packed in the graph?
• Is it possible to solve graph coloring and computing maximum independent sets in polynomial time on even-hole-free graphs?

Other lists of open problems¶

• Open Problems - Graph Theory and Combinatorics
• Current Research Problems (William T. Trotter)
• List of unsolved problems in computer science (Wikipedia)
• Open Problem Garden
• Open problems on TCS.SE
• Major unsolved problems in theoretical computer science? (TCS.SE)
• Autobóz: Open Problems
• The PolyTCS project
• Are there any open problems left about DFAs?
• Open Problems in Sublinear Algorithms
• Not especially famous, long-open problems which anyone can understand
• The Open Problems Project
• Open problems in twin-width

Here are links to some other specific open questions found on other places on the Web:

• Équivalence des représentations de polyèdres convexes (in French)

Solved problems¶

This section regroups problems that occurred in a previous version of this list, and were solved since then.

Complexity of an assignment problem with subsets¶

It is known that a maximum matching can be found in PTIME. In particular, this is the case of bipartite graphs. However, what about the situation where we are allowed to remove vertices in one of the parts, and where we want to maximize the number of vertices that must remain unmatched in a maximum matching? What is the complexity of this problem?

• TCS.SE question with precise statement

Proved to be in PTIME by Chao Xu in this TCS.SE answer. Thanks!

Decidability of conjunctive query determinacy in the finite¶

The query determinacy problem asks, given a set $Q_1,\dots ,Q_n$ of conjunctive queries (CQs) and an additional CQ $Q$, whether the $Q_i$ determine $Q$, i.e., whether, for any two (possibly infinite) relational databases $I$ and $I^{\prime }$, having $Q_i\left(I\right)=Q_i\left(I^{\prime }\right)$ for all $1\le i\le n$ implies we must have $Q\left(I\right)=Q\left(I^{\prime }\right)$. The query determinacy problem was shown⁴³ to be undecidable but this work left open the problem of finite determinacy, which is defined as determinacy except that $I$ and $I^{\prime }$ must be finite.

Is finite determinacy also undecidable for conjunctive queries?

Proved by the authors of the original work⁴³ in a new paper. As this was accepted for publication at PODS 2016, I think we can say that this has been accepted by the community, although I haven't personally checked the proof.

Steinberg's conjecture¶

Grötzch's theorem says that planar graphs without 3-cycles (triangles) are 3-colorable. Is every planar graph without 4-cycles and 5-cycles 3-colorable?

• The question on Open Problem Garden

Disproved in this paper. I haven't personally checked it, but it has been published in the Journal of Combinatorial Theory, so I'm assuming it is correct.

Feder-Vardi conjecture¶

Letting $\Gamma$ be a digraph, the CSP for $\Gamma$, written $\text{CSP}\left(\Gamma \right)$, is the following problem: given a digraph $G$, decide whether there is a homomorphism from $G$ to $\Gamma$. The Feder-Vardi conjecture³⁴ asks: Is there a dichotomy on $\Gamma$, with $\text{CSP}\left(\Gamma \right)$ being always either in PTIME or NP-hard?

An analogous result is already known for undirected graphs³⁵, for some restricted classes of directed graphs³⁶, and when $\Gamma$ has two elements³⁷ or more recently three elements³⁸.

Proved: two recent preprints by Bulatov and by Zhuk claim a proof of this result. The papers were accepted for publication at FOCS 2017 so I'm classifying this as solved (accepted by the community), even though it may still be a good idea to verify these proofs in more detail (see this post). I have not personally checked any of this.

Thanks to Mikaël Monet for pointing out that the conjecture for digraphs implies³⁹ the conjecture for relational structures.

Complexity of counting linear extensions in posets of height 2¶

It is #P-hard to count the number of linear extensions of an input poset². The proof uses posets of height 3, and leaves open the natural question: is it #P-hard to count linear extensions in posets of height 2?

An equivalent formulation is in terms of directed bipartite graphs (all edges go from one part to the other part): given a directed bipartite graph as input, is it #P-hard to count the number of topological sorts of the graph?

Solved in this paper (shown to be #P-hard). Note that I haven't personally checked it. Thanks to Kuldeep S. Meel for pointing me to that paper.

Complexity of counting linear extensions in posets of dimension 2¶

This is similar to the question above, but for order dimension: is it #P-hard to count linear extensions in posets of dimension 2?

Solved in the same paper as above (shown to be #P-hard).

The monk problem¶

The so-called monk problem¹² is a pursuit-evasion game played on a directed graph. A strategy for $k$ pursuers is a sequence $s_1,\dots ,s_n$ of subsets of $k$ vertices. A strategy is winning if, for every (non-simple) walk $v_1,\dots ,v_n$ in the graph, there is $i$ such that $v_i\in s_i$. Intuitively, the evader is walking on the graph (it has to move at each turn by following exactly one edge) and must avoid the $k$ vertices that the pursuers examine at each time step.

The evasion number of a digraph $G$ is the smallest $k$ for which the pursuers have a winning strategy. What is the computational complexity, given an input digraph, of computing its evasion number?

Solved in this paper: it is already NP-hard to check if an input digraph has evasion number 1.

Retired problems¶

This section contains former questions which I no longer think are interesting or sensible, or for which my interest has waned.

What is the connection between the fluted fragment and inversion-free queries?¶

The fluted fragment is a fragment of function-free first-order logic for which the satisfiability problem is decidable¹³ (but non-elementary). This definition is reminiscent of inversion-free queries, which are known¹⁴ to be exactly the UCQs that admit OBDD lineages on TID databases (see this question for relevant definitions).

Is there any connection between these two classes?

The original version of this question incorrectly claimed that inversion-free queries are the positive existential fragment of fluted queries, but this is in fact not correct: there are non-hierarchical CQs, e.g., $\exists xyR\left(x\right),S(x,y),T\left(y\right)$, which are fluted. So while there is still a connection in the definitions, the link is no longer as compelling, and I don't think the question is so interesting anymore.

Thanks to the anonymous Reviewer 3 of our paper at PODS 2016 for pointing out this connection. Thanks to Bartosz Bednarczyk for bringing back this problem to my attention, which made me realize the error.

Compactness difference between probabilistic XML document formalisms¶

The PrXML formalism is a way to represent probability distribution on labeled, unranked, unordered trees⁵⁶. It does so by representing uncertainty with special kinds of nodes:

• ind nodes have each child labeled with a probability in $[0,1]$ indicating the probability (independently across draws) that the child node is kept, or that it is discarded along with its descendants; the ind node is replaced by the collection of its kept children;
• mux nodes have each child labeled with a probability in $[0,1]$, the probabilities summing to at most $1$, and one of the children is kept by drawing according to the probabilities (if the sum is $<1$ there is a probability of keeping no child); the children that are not kept are removed with their descendants, and the mux node is replaced by its kept child (if any);
• det nodes are deterministically replaced by the collection of their children;
• cie nodes have their children labeled by a conjunction of Boolean variables from a global set of variables, where each variable has some probability in $[0,1]$ of being true (the same variables can be used in multiple cie nodes); the semantics is that a valuation for the variables is drawn by setting each variable as true or false with the indicated probabilities, independently, and replacing each cie node by the children whose edge annotation evaluates to true under the chosen variable valuation;
• exp nodes are annotated with an explicit probability distribution: a set of pairs of a subset of children of the nodes and a probability, the probabilities summing to 1.

We give names to families of probabilistic XML documents according to the nodes that are allowed, e.g., PrXML^{ind, mux} refers to probabilistic documents where nodes of type ind and mux are allowed. A family is efficiently translatable in another if any document of the first family can be rewritten to a document in the second. Some families are known to be efficiently translatable in others⁵⁷, but open questions remain: is PrXML^exp efficiently translatable in PrXML^mux,det, or even to PrXML^cie?

Thanks to Pierre Senellart for helping me to prepare this entry.

Complexity of testing the equivalence of PrXML^cie¶

Using the previous definitions, the semantic equivalence problem for two PrXML documents asks whether the two documents define the same probability distribution on outcomes (same possible worlds, with same probabilities). Given two PrXML^cie documents, what is the probability of deciding whether they are semantically equivalent? The problem is in EXPTIME but no lower bound or hardness result is known⁵⁸. What is the complexity of this problem?

The structural equivalence problem asks, given two PrXML^cie documents, whether, for each valuation of the variables, the corresponding valuations of both documents are the same. (Note that the probabilities assigned to the events is irrelevant.) The problem is in coNP, but no lower bound or hardness result is known⁵⁹. What is the complexity of this problem?

Thanks to Pierre Senellart for helping me to prepare this entry.