Author name cluster

Katrin Casel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

AAMAS Conference 2025 Conference Paper

Emit As You Go: Enumerating Edges of a Spanning Tree

Katrin Casel
Stefan Neubert

Classically, planning tasks are studied as a two-step process: plan creation and plan execution. In situations where plan creation is slow (for example, due to expensive information access or complex constraints), a natural speed-up tactic is interleaving planning and execution. We implement such an approach with an enumeration algorithm that, after little preprocessing time, outputs parts of a plan one by one with little delay in-between consecutive outputs. As concrete planning task, we consider efficient connectivity in a network formalized as the minimum spanning tree problem in all four standard variants: (un)weighted (un)directed graphs. Solution parts to be emitted one by one for this concrete task are the individual edges that form the final tree. We show with algorithmic upper bounds and matching unconditional adversary lower bounds that efficient enumeration is possible for three of four problem variants; specifically for undirected unweighted graphs (delay in the order of the average degree), as well as graphs with either weights (delay in the order of the maximum degree and the average runtime per emitted edge of a total-time algorithm) or directions (delay in the order of the maximum degree). For graphs with both weighted and directed edges, we show that no meaningful enumeration is possible. Finally, with experiments on random undirected unweighted graphs, we show that the theoretical advantage of little preprocessing and delay carries over to practice.

PDF

ICAPS Conference 2024 Conference Paper

Incremental Ordering for Scheduling Problems

Stefan Neubert
Katrin Casel

Given an instance of a scheduling problem where we want to start executing jobs as soon as possible, it is advantageous if a scheduling algorithm emits the first parts of its solution early, in particular before the algorithm completes its work. Therefore, in this position paper, we analyze core scheduling problems in regards to their enumeration complexity, i. e. the computation time to the first emitted schedule entry (preprocessing time) and the worst case time between two consecutive parts of the solution (delay). Specifically, we look at scheduling instances that reduce to ordering problems. We apply a known incremental sorting algorithm for scheduling strategies that are at their core comparison-based sorting algorithms and translate corresponding upper and lower complexity bounds to the scheduling setting. For instances with n jobs and a precedence DAG with maximum degree Δ, we incrementally build a topological ordering with O(n) preprocessing and O(Δ) delay. We prove a matching lower bound and show with an adversary argument that the delay lower bound holds even in case the DAG has constant average degree and the ordering is emitted out-of-order in the form of insert operations. We complement our theoretical results with experiments that highlight the improved time-to-first-output and discuss research opportunities for similar incremental approaches for other scheduling problems.

Details

TCS Journal 2022 Journal Article

On the complexity of solution extension of optimization problems

Katrin Casel
Henning Fernau
Mehdi Khosravian Ghadikolaei
Jérôme Monnot
Florian Sikora

The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal vertex covers of a graph G = ( V, E ), one usually arrives at the problem to decide for a vertex set U ⊆ V (pre-solution), if there exists a minimal vertex cover S (i. e. , a vertex cover S ⊆ V such that no proper subset of S is a vertex cover) with U ⊆ S (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework. In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP -complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP -completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework.

Details DOI

TCS Journal 2018 Journal Article

The many facets of upper domination

Cristina Bazgan
Ljiljana Brankovic
Katrin Casel
Henning Fernau
Klaus Jansen
Kim-Manuel Klein
Michael Lampis
Mathieu Liedloff

This paper studies Upper Domination, i. e. , the problem of computing the maximum cardinality of a minimal dominating set in a graph with respect to classical and parameterised complexity as well as approximability.

Details DOI

MFCS Conference 2017 Conference Paper

Combinatorial Properties and Recognition of Unit Square Visibility Graphs

Katrin Casel
Henning Fernau
Alexander Grigoriev
Markus L. Schmid
Sue Whitesides

Unit square (grid) visibility graphs (USV and USGV, resp.) are described by axis-parallel visibility between unit squares placed (on integer grid coordinates) in the plane. We investigate combinatorial properties of these graph classes and the hardness of variants of the recognition problem, i. e. , the problem of representing USGV with fixed visibilities within small area and, for USV, the general recognition problem.

Details

Highlights Conference 2016 Conference Abstract

On the Complexity of Grammar-Based Compression over Fixed Alphabets

Katrin Casel
Henning Fernau
Serge Gaspers
Benjamin Gras
Markus L. Schmid

This talk is based on the following paper: Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid. On the Complexity of Grammar-Based Compression over Fixed Alphabets. 43rd International Colloquium on Automata, Languages, and Programming 2016, ICALP 2016. We investigate the complexity of grammar-based compression, i. e. , to compress a word by a context-free grammar. It is shown that the shortest-grammar problem remains NP-complete if the alphabet is fixed and has a size of at least 24 (which settles an open question). On the other hand, this problem can be solved in polynomial-time, if the number of nonterminals is bounded, which is shown by encoding the problem as a problem on graphs with interval structure. Furthermore, we present an O(3^n) exact exponential-time algorithm, based on dynamic programming. Similar results are also given for 1-level grammars, i. e. , grammars for which only the start rule contains nonterminals on the right side (thus, investigating the impact of the “hierarchical depth” on the complexity of the shortest-grammar problem).

Details