Invited Talks
Gregory Gutin
Royal Holloway, University of London, UK
Title: Parameterized Graph Coloring Problems
Abstract: Graph coloring is a central topic in Computer Science due to a significant interest
in the problems from both theoretical and practical points of view.
Unfortunately, these problems are well-known to be intractable. We will discuss
parameterized complexity approaches to the problems and related algorithms
and lower bounds. In particular, we will discuss the following recent results
obtained by Majumdar, Ordyniak, Wahlstrom and the speaker on parameterized
List Coloring and Pre-coloring problems.
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the
parameterized complexity of the following problems parameterized by
k: (1) Given a graph G, a clique modulator D (a clique modulator is a set of
vertices, whose removal results in a clique) of size k for G, and a list L(v)
of colors for every vertex v of G, decide whether G has a proper list coloring;
(2) Given a graph G, a clique modulator D of size k for G, and a pre-coloring
\lambda_P: X \to Q for X \subseteq V(G), decide whether \lambda_P can be extended
to a proper coloring of G using only colors from Q. For Problem 1 we designed
an O^*(2^k)-time randomized algorithm and for Problem 2 we obtained a kernel
with at most 3k vertices. Banik, Jacob, Paliwal and Raman (IWOCA 2019) proved that
the following problem is fixed-parameter tractable and asked whether it admits
a polynomial kernel: Given a graph G, an integer k, and a list L(v) of exactly
n-k colors for every vertex v of G decide whether there is a proper list coloring for G. We obtained a kernel with O(k^2) vertices and colors and a compression to a variation of the problem with O(k) vertices and O(k^2) colors.
Solon P. Pissis
Centrum Wiskunde & Informatica (CWI)
Title: Combinatorial Algorithms for String Sanitization
Abstract: Data sanitization is the process of disguising confidential information with realistic but false data. The Combinatorial String Dissemination (CSD) model was recently introduced to realise utility-preserving string sanitization effectively. In this talk, we will describe the CSD model and provide relevant formulations of the string sanitization problem as a combinatorial problem with a set of privacy constraints and a set of application-specific utility properties. We will then review some algorithmic results for these problem formulations. Our main ingredients are string and graph algorithms: string tools to unveil the combinatorial structure of the input string; and graph algorithms as combinatorial optimisation tools to ensure that the sanitized string satisfies both the set of constraints and the set of desirable properties.
Dana Shapira
Ariel University, Israel
Title: Better Than Optimal Huffman Coding
Abstract: Huffman coding is known to be optimal, yet its dynamic version may yield smaller compressed files. The best known bound is that
the number of bits used by dynamic Huffman coding in order
to encode a message of n characters is at most larger by n bits than the size of the file required by static Huffman coding.
In particular, dynamic Huffman coding can also generate a larger encoded file than the static variant, though in practice the file might sometimes be smaller. We propose a new adaptive encoding approach, that provably always performs better than
static Huffman coding by at least m-1 bits, where m denotes the size of the alphabet, and may be better than the standard dynamic Huffman coding for certain files. This is achieved by reversing the direction for the references of the encoded elements to those forming the model of the encoding, from pointing backwards into the past to looking forward into the future.
Empirical results implementing this "forward looking" approach based on Huffman and arithmetic coding support our theoretical improvement also in practice.
