Raziskovalni matematični seminar - Arhiv

The First Koper - Bahia Blanca Workshop on Structural and Algorithmic Graph Theory
UP FAMNIT, Glagoljaska 8, Koper, Velika predavalnica
Wednesday, July 4, 2018, 9:30-12:00

9:30-10:00 Nevena Mitrovic (University of Primorska), On the End-Vertex Problem
10:00-10:30 Martin Safe (Universidad Nacional del Sur, Bahia Blanca, Argentina), Convex p-partitions of bipartite graphs
10:30-11:00 break 
11:00-11:30 Martin Milanic (University of Primorska), 1-Sperner hypergraphs and new characterizations of threshold graphs
11:30-12:00 Nina Chiarelli (University of Primorska), Improved algorithms for k-domination and total k-domination in proper interval graphs

======================================================
ABSTRACTS OF TALKS
======================================================

Nevena Mitrovic, On the End-Vertex Problem

For a given graph search algorithm and a graph G, a vertex v is said to be an end-vertex if there exists a corresponding search ordering of the vertices such that v is the last vertex in this ordering. It is known that the complexity of recognizing the end-vertices in general graphs is NP-hard for several search algorithms, such as Breadth First search, Depth First Search, and their lexicographic variants. This motivated the study of end-vertices with respect to some other search algorithms. In this work we consider the Maximum Cardinality Search (MCS) and the Maximum Neighborhood Search (MNS) and present the results concerning complexity of the end-vertex problem with respect to these search methods.

The talk is based on joint work with Jesse Beisegel, Carolin Denkert, Ekkehard Koehler, Matjaz Krnc, Robert Scheffler, and Martin Strehler.
(An extended abstract of this work will be published in the proceedings of ICGT 2018.)

======================================================

Martin Safe, Convex p-partitions of bipartite graphs

A set X of vertices in a graph is convex if no shortest path between two vertices in X contains a vertex outside of X. A convex p-partition of a graph is a partition of its vertex set into p nonempty convex sets. It is known that, for each integer p greater than or equal to 2, deciding whether any given graph has a convex p-partition is an NP-complete problem. We show that, for each fixed positive integer p, all convex p-partition of any given bipartite graph G can be enumerated in polynomial time.

This is joint work with Luciano Grippo, Martin Matamala, and Maya Stein.

Reference:
Grippo, Luciano N., Martin Matamala, Martin D. Safe, and Maya J. Stein. Convex p-partitions of bipartite graphs. Theoretical Computer Science 609 (2016): 511-514.
https://doi.org/10.1016/j.tcs.2015.11.014

======================================================

Martin Milanic, 1-Sperner hypergraphs and new characterizations of threshold graphs

A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable (resp., threshold) if the characteristic vectors of its hyperedges are the (minimal) binary solutions to a linear equation (resp., inequality) with positive coefficients. These combinatorial notions have many applications and are motivated by the theory of Boolean functions and integer programming. We introduce the class of 1-Sperner hypergraphs, defined by the property that for every two hyperedges the smallest of their two set differences is of size one. We characterize this class of Sperner hypergraphs by a decomposition theorem and derive several consequences from it. Furthermore, we present several applications of 1-Sperner hypergraphs and their structure to graphs. In particular, we consider the classical characterizations of threshold and domishold graphs and use them to obtain further characterizations of these classes in terms of 1-Spernerness, thresholdness, and 2-asummability of their vertex cover, clique, dominating set, and closed neighborhood hypergraphs. 

The talk is based on joint work with Endre Boros and Vladimir Gurvich.

Link to preprints: 
https://arxiv.org/abs/1510.02438
https://arxiv.org/abs/1805.03405

======================================================

Nina Chiarelli, Improved algorithms for k-domination and total k-domination in proper interval graphs
 
Given a positive integer k, a k-dominating set in a graph G is a set of vertices such that every vertex not in the set has at least k neighbors in the set. A total k-dominating set, also known as a k-tuple total dominating set, is a set of vertices such that every vertex of the graph has at least k neighbors in the set. The problems of finding the minimum size of a k-dominating, resp. total k-dominating set, in a given graph, are referred to as k-domination, resp. total k-domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total k-domination). On the other hand, it follows from recent work by Kang et al. (2017) that these two families of problems are solvable in time O(|V(G)|^{6k+4}) in the class of interval graphs. In this work, we develop faster algorithms for k-domination and total k-domination in the class of proper interval graphs. The algorithms run in time O(|V(G)|^{3k}) for each fixed k >= 1 and are also applicable to the weighted case. 

The talk is based on joint work with Tatiana Romina Hartinger, Valeria Alejandra Leoni, Maria Ines Lopez Pujato, and Martin Milanic.

Link to preprint: https://arxiv.org/abs/1803.04327
(An extended abstract will be published in the proceedings of ISCO 2018.)