Seminar on Foundations of Computing

Michal Dvořák : Pathfinding in Self-Deleting Graphs

Monday, September 29, 14:00

We study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we study self-deleting graphs, introduced by Carmesin et al. (Sarah Carmesin, David Woller, David Parker, Miroslav Kulich, and Masoumeh Mansouri), which consist of a graph G=(V, E) and a function f: V->2^E, where f(v) is the set of edges that will be deleted after visiting the vertex v. In the (Shortest) Self-Deleting s-t-path problem we are given a self-deleting graph and its vertices s and t, and we are asked to find a (shortest) path from s to t, such that it does not traverse an edge in f(v) after visiting v for any vertex v.

We prove that Self-Deleting s-t-path is NP-hard even if the given graph is outerplanar, bipartite, has maximum degree 3, bandwidth 2 and |f(v)| ≤ 1 for each vertex v. We show that Shortest Self-Deleting s-t-path is W[1]-complete parameterized by the length of the sought path and that Self-Deleting s-t-path is W[1]-complete parameterized by the vertex cover number, feedback vertex set number and treedepth. We also show that the problem becomes FPT when we parameterize by the maximum size of f(v) and several structural parameters. Lastly, we show that the problem does not admit a polynomial kernel even for parameterization by the vertex cover number and the maximum size of f(v) combined already on 2-outerplanar graphs.

Daniela Černá : Shattering triples with six permutations and related problems

Monday, October 6, 14:00

Let n≥3 be an integer and (π₁,π₂,π₃, π₄, π₅, π₆) be six permutations of the same ground set [n]. We say that the triple {aπ₁, a₂, a₃}⊂[n] is shattered by (π₁,π₂,π₃, π₄, π₅, π₆) if we can find all possible orderings in the set {(π_i(a₁),π_i(a₂),π_i(a₃)):i∈[6]}.

A natural extremal question is to determine the maximal possible number of triples that can be shattered in this way for a fixed n.

Using the flag algebra method, we prove that no six-tuple of permutations shatters more than 1/2 C(n,3) O(n²) triples. On the other hand, for every n≥3, we construct six permutations of [n] that shatter at least 975/482 C(n,30) triples. We also determine exact values for n∈{6,7,8,9}. These results improve the previously known bounds of Johnson and Wickes.

Next, we focus on related problems, where we add more restrictions on the six-tuple (π₁,π₂,π₃, π₄, π₅, π₆).

This is a joint work with Alexander Clifton, Bartłomiej Kielak, and Jan Volec.

Aneta Pokorná: Reconstructing graphs using graphlet degree sequences

Monday, October 10, 14:00

Graphlets are small subgraphs rooted at a fixed vertex. The number of occurrences of graphlets aligned to a particular vertex, called graphlet degree sequence, gives a topological description of the surrounding of the analyzed vertex.

A long standing open problem in graph theory, the reconstruction conjecture, asks whether the structure of a graph is uniquely determined by its vertex-deleted subgraphs. We ask whether the structure of a graph G is uniquely determined by the graphlet degree sequences of its vertices (considering all graphlets smaller than G). We'll show that the answer is positive for graphs having certain type of asymmetric vertex-deleted subgraphs. Note that the idea of using asymmetry is novel even among the partial results for the (harder) reconstruction from vertex-deleted subgraphs.

Sabine Rieder: Decision Tree Explanations in the Context of Machine Learning

Monday, October 27, 14:00

Trust in a decision-making system requires both safety guarantees and the ability to interpret and understand its behavior. This is particularly important for learned systems, whose decision-making processes are often highly opaque. Recently, decision trees have become customary for representing controllers and policies.

In this talk, we investigate two directions in which decision trees can be used to explain RL systems. The first application area is shielding. Shielding is a prominent model-based technique for enforcing safety in reinforcement learning. However, because shields are automatically synthesized using rigorous formal methods, their decisions are often similarly difficult for humans to interpret and inherently non-deterministic. Therefore, their decision tree representations become too large to be explainable in practice. To address this challenge, we propose a novel approach for explainable safe RL that enhances trust by providing human-interpretable explanations of the shield’s decisions. Our method represents the shielding policy as a hierarchy of decision trees, offering top-down, case-based explanations.

Secondly, we consider concept-based explanations of neural networks, where the nodes in the DT correspond to a semantic concept in the NN. In contrast to previous work, our explanations focus on fidelity with respect to the original network.

Tomáš Hons: A Polynomial Ramsey Statement for Bounded VC-dimension

Monday, November 3, 14:00

A theorem by Ding, Oporowski, Oxley, and Vertigan states that every sufficiently large bipartite graph without twins contains a matching, co-matching, or half-graph of any given size as an induced subgraph. We prove that this Ramsey statement has polynomial dependency assuming bounded VC-dimension of the initial graph, using the recent verification of the Erdős-Hajnal property for graphs of bounded VC-dimension. Since the theorem of Ding et al. plays a role in (finite) model theory, which studies even more restricted structures, we also comment on further refinements of the theorem within this context.