Raziskovalni matematični seminar - Arhiv

Given an undirected graph G=(V, E), two vertices s,t∈ V, and two integers k,l, the Short Secluded Path problem asks whether there exists an s-t path of length at most k with at most l neighbors. The "secluded" problems are motivated by finding structures with little interference, secure structures, or isolated structures. From a parameterized complexity perspective, the Short Secluded Path problem is W[1]-hard when parameterized by k or cliquewidth, while it is fixed-parameter tractable when parameterized by treewidth (how a graph is close to a tree structure). In this paper, we discuss the structural parameterization of the Short Secluded Path problem using dense graph parameters such as cliquewidth (a generalization of treewidth), twin cover number (a generalization of vertex cover; how a graph is close to disjoint union of cliques considering neighborhoods), and neighborhood diversity (how many neighborhood structures a graph has). We show that Short Secluded Path has an XP algorithm by cliquewidth, FPT algorithms by twin cover number and neighborhood diversity, respectively. Furthermore, we introduce the Short Secluded Path problem, which aims to find a shortest s-t path with the minimum number of neighbors. We show that this problem can be solved in polynomial time.

Combinatorial games have been studied since the early 20^th century. In 1970, Sato showed that a game introduced by Welter in the 1950's could be viewed as a game on integer partitions. He conjectured that the Sprague-Grundy values of this game are related to the irreducible representations of the symmetric group. This conjecture has since been resolved in the affirmative. I will describe this game as well as some others that can be played on integer partitions. I will mention some results and open questions associated with these games, including their locations in the Conway-Gurvich-Ho classification.

This is joint work with Matjaž Krnc, Peter Muršič, Ina Bašić, Hannah Meit, and a number of other current and former students from my home institution. 

Numerous finite games can be played on a directed graph, and the existence of a stationary (positional) equilibrium is always an interesting and challenging question. In shortest path games two players try to find a "shortest" path between two specified vertices of the given graph. However, the two players have their own, distinct ways of measuring distance. We prove the existence of a stationary equilibrium by using multiple potential transformations on the given graph, and arguing with the already known zero-sum case. 

Joint research with K. Elbassioni, V. Gurvich and M. Vyalyi.