Jörg Flum

I&C Journal 2025 Journal Article

On algorithms based on finitely many homomorphism counts

• Yijia Chen
• Jörg Flum
• Mingjun Liu
• Zhiyang Xun

It is a well-known result of Lovász that up to isomorphism a graph G is determined by the homomorphism counts hom ( F, G ), i. e. , the number of homomorphisms from F to G, where F ranges over all graphs. Thus, in principle, we can answer any query concerning G with only accessing the hom ( ⋅, G ) 's instead of G itself. In this paper, we deal with queries φ for which there is a hom algorithm, i. e. , there are finitely many graphs F 1, …, F k such that for any graph G whether it is a Yes-instance of the query is already determined by the vector hom → F 1, …, F k ( G ): = ( hom ( F 1, G ), …, hom ( F k, G ) ), where the graphs F 1, …, F k only depend on φ. We observe that planarity of graphs and 3-colorability of graphs, properties expressible in monadic second-order logic, have no hom algorithm. We provide a characterization of the prefix classes of first-order logic with the property that each query definable by a sentence of the prefix class has a hom algorithm. For adaptive query algorithms, i. e. , algorithms that again access hom → F 1, …, F k ( G ) but here F i + 1 might depend on hom ( F 1, G ), …, hom ( F i, G ), we show that three homomorphism counts hom ( ⋅, G ) are both sufficient and in general necessary to determine the isomorphism type of G.

MFCS Conference 2022 Conference Paper

On Algorithms Based on Finitely Many Homomorphism Counts

• Yijia Chen 0001
• Jörg Flum
• Mingjun Liu 0003
• Zhiyang Xun

It is well known [L. Lovász, 1967] that up to isomorphism a graph G is determined by the homomorphism counts hom(F, G), i. e. , by the number of homomorphisms from F to G where F ranges over all graphs. Moreover, it suffices that F ranges over the graphs with at most as many vertices as G. Thus, in principle, we can answer any query concerning G with only accessing the hom(⋅, G)’s instead of G itself. In this paper, we deal with queries for which there is a hom algorithm, i. e. , there are finitely many graphs F₁, …, F_k such that for any graph G whether it is a Yes-instance of the query is already determined by the vector hom^⟶_{F₁, …, F_k}(G): = (hom(F₁, G), …, hom(F_k, G)). We observe that planarity of graphs and 3-colorability of graphs, properties expressible in monadic second-order logic, have no hom algorithm. On the other hand, queries expressible as a Boolean combination of universal sentences in first-order logic FO have a hom algorithm. Even though it is not easy to find FO definable queries without a hom algorithm, we succeed to show this for the non-existence of an isolated vertex, a property expressible by the FO sentence ∀ x∃ y Exy, somehow the "simplest" graph property not definable by a Boolean combination of universal sentences. These results provide a characterization of the prefix classes of first-order logic with the property that each query definable by a sentence of the prefix class has a hom algorithm. For adaptive hom algorithms, i. e. , algorithms that might access a hom(F_{i+1}, G) with F_{i+1} depending on hom(F_j, G) for 1 ≤ j ≤ i we show that three homomorphism counts hom(⋅, G) are sufficient and in general necessary to determine the (isomorphism type of) G. In particular, by three adaptive queries we can answer any question on G. Moreover, adaptively accessing two hom(⋅, G)’s is already enough to detect an isolated vertex. In 1993 Chaudhuri and Vardi [S. Chaudhuri and M. Y. Vardi, 1993] showed the analogue of the Lovász Isomorphism Theorem for the right homomorphism vector of a graph G, i. e, the vector of values hom(G, F) where F ranges over all graphs characterizes the isomorphism type of G. We study to what extent our results carry over to the right homomorphism vector.

CSL Conference 2020 Conference Paper

FO-Definability of Shrub-Depth

• Yijia Chen 0001
• Jörg Flum

Shrub-depth is a graph invariant often considered as an extension of tree-depth to dense graphs. We show that the model-checking problem of monadic second-order logic on a class of graphs of bounded shrub-depth can be decided by AC^0-circuits after a precomputation on the formula. This generalizes a similar result on graphs of bounded tree-depth [Y. Chen and J. Flum, 2018]. At the core of our proof is the definability in first-order logic of tree-models for graphs of bounded shrub-depth.

I&C Journal 2019 Journal Article

Some lower bounds in parameterized AC0

• Yijia Chen
• Jörg Flum

We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical AC 0. Among others, we derive such a lower bound for all fpt-approximations of the parameterized clique problem and for a parameterized halting problem, which recently turned out to link problems of computational complexity, descriptive complexity, and proof theory. To show the lower bound mentioned first we prove a strong AC 0 version of the planted clique conjecture: AC 0 -circuits asymptotically almost surely can not distinguish between a random graph and this graph with a randomly planted clique of any size ≤ n ξ (where 0 ≤ ξ < 1 ).

CSL Conference 2017 Conference Paper

Slicewise Definability in First-Order Logic with Bounded Quantifier Rank

• Yijia Chen 0001
• Jörg Flum
• Xuangui Huang

For every natural number q let FO_q denote the class of sentences of first-order logic FO of quantifier rank at most q. If a graph property can be defined in FO_q, then it can be decided in time O(n^q). Thus, minimizing q has favorable algorithmic consequences. Many graph properties amount to the existence of a certain set of vertices of size k. Usually this can only be expressed by a sentence of quantifier rank at least k. We use the color coding method to demonstrate that some (hyper)graph problems can be defined in FO_q where q is independent of k. This property of a graph problem is equivalent to the question of whether the corresponding parameterized problem is in the class para-AC^0. It is crucial for our results that the FO-sentences have access to built-in addition and multiplication (and constants for an initial segment of natural numbers whose length depends only on k). It is known that then FO corresponds to the circuit complexity class uniform AC^0. We explore the connection between the quantifier rank of FO-sentences and the depth of AC^0-circuits, and prove that FO_q is strictly contained in FO_{q+1} for structures with built-in addition and multiplication.

MFCS Conference 2016 Conference Paper

Some Lower Bounds in Parameterized AC^0

• Yijia Chen 0001
• Jörg Flum

We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical AC^0. Among others, we derive such a lower bound for all fpt-approximations of the parameterized clique problem and for a parameterized halting problem, which recently turned out to link problems of computational complexity, descriptive complexity, and proof theory. To show the first lower bound, we prove a strong AC^0 version of the planted clique conjecture: AC^0-circuits asymptotically almost surely can not distinguish between a random graph and this graph with a randomly planted clique of any size <= n^xi (where 0 <= xi < 1).

MFCS Conference 2011 Invited Paper

Invariantization of Listings

• Jörg Flum

Abstract We consider a halting problem for nondeterministic Turing machines and show via invariantization of listings the relationship of its complexity to the existence of almost optimal algorithms for the set of propositional tautologies; the existence of hard sequences for all algorithms deciding a given problem; the existence of logics capturing polynomial time.

CSL Conference 2010 Conference Paper

On Slicewise Monotone Parameterized Problems and Optimal Proof Systems for TAUT

• Yijia Chen 0001
• Jörg Flum

Abstract For a reasonable sound and complete proof calculus for first-order logic consider the problem to decide, given a sentence ϕ of first-order logic and a natural number n, whether ϕ has no proof of length ≤ n. We show that there is a nondeterministic algorithm accepting this problem which, for fixed ϕ, has running time bounded by a polynomial in n if and only if there is an optimal proof system for the set TAUT of tautologies of propositional logic. This equivalence is an instance of a general result linking the complexity of so-called slicewise monotone parameterized problems with the existence of an optimal proof system for TAUT.

CSL Conference 2007 Conference Paper

Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping

• Yijia Chen 0001
• Jörg Flum

Abstract Recently a mapping, the so-called miniaturization mapping, has been introduced and it has been shown that faithfully translates subexponential parameterized complexity into (unbounded) parameterized complexity [2]. We determine the preimages under of various (classes of) problems and show that they coincide with natural reparameterizations which take into account the amount of nondeterminism needed to solve them.

TCS Journal 2006 Journal Article

On miniaturized problems in parameterized complexity theory

• Yijia Chen
• Jörg Flum

We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W [ t ] lies in W [ t ], too. In particular, the miniaturization of the dominating set problem is in W [ 2 ]. Furthermore, we investigate the relation between f ( k ) · n o ( k ) time and subexponential time algorithms for the dominating set problem and for the clique problem.

TCS Journal 2005 Journal Article

Machine-based methods in parameterized complexity theory

• Yijia Chen
• Jörg Flum
• Martin Grohe

We give machine characterizations of most parameterized complexity classes, in particular, of W[P], of the classes of the W-hierarchy, and of the A-hierarchy. For example, we characterize W[P] as the class of all parameterized problems decidable by a nondeterministic fixed-parameter tractable algorithm whose number of nondeterministic steps is bounded in terms of the parameter. The machine characterizations suggest the introduction of a hierarchy W func between the W- and the A-hierarchy. We study the basic properties of this hierarchy.

I&C Journal 2003 Journal Article

Describing parameterized complexity classes

• Jörg Flum
• Martin Grohe

We describe parameterized complexity classes by means of classical complexity theory and descriptive complexity theory. For every classical complexity class we introduce a parameterized analogue in a natural way. In particular, the analogue of polynomial time is the class of all fixed-parameter tractable problems. We develop a basic complexity theory for the parameterized analogues of classical complexity classes and give, among other things, complete problems and logical descriptions. We then show that most of the well-known intractable parameterized complexity classes are not analogues of classical classes. Nevertheless, for all these classes we can provide natural logical descriptions.

CSL Conference 2003 Conference Paper

Machine Characterization of the Classes of the W-Hierarchy

• Yijia Chen 0001
• Jörg Flum

Abstract We give machine characterizations of the complexity classes of the W-hierarchy. Moreover, for every class of this hierarchy, we present a parameterized halting problem complete for this class.

FOCS Conference 2002 Conference Paper

The Parameterized Complexity of Counting Problems

• Jörg Flum
• Martin Grohe

We develop a parameterized complexity theory for counting problems. As the basis of this theory, we introduce a hierarchy of parameterized counting complexity classes #W[t], for t/spl ges/1, that corresponds to Downey and Fellows' (1999) W-hierarchy and show that a few central W-completeness results for decision problems translate to #W-completeness results for the corresponding counting problems. Counting complexity gets interesting with problems whose decision version is tractable, but whose counting version is hard. Our main result states that counting cycles and paths of length k in both directed and undirected graphs, parameterized by k, are #W[1]-complete. This makes it highly unlikely that any of these problems is fixed-parameter tractable, even though their decision versions are. More explicitly, our result shows that most likely there is no f(k)/spl middot/n/sup c/-algorithm for counting cycles or paths of length k in a graph of size n for any computable function f: /spl Nopf//spl rarr//spl Nopf/ and constant c, even though there is a 2/sup O(k)//spl middot/n/sup 2. 376/ algorithm for finding a cycle or path of length k (2).

TCS Journal 2000 Journal Article

Games and total Datalog¬ queries

• Jörg Flum
• Max Kubierschky
• Bertram Ludäscher

We show that the expressive power of Datalog ¬ programs under the well-founded semantics does not decrease when restricted to total programs thereby affirmatively answering an open question posed by Abiteboul et al. (Foundations of Databases, Addison-Wesley, Reading, MA, 1995). In particular, we show that for every such program there exists an equivalent total program whose only recursive rule is of the form win( X ̄ )←move( X ̄, Y ̄ ), ¬win( Y ̄ ), where move is definable by a quantifier-free first-order formula. Also, for the noninflationary semantics we derive a new normal form whose only recursive rule simulates a version of the game of life.

CSL Conference 1992 Conference Paper

On Bounded Theories

• Jörg Flum