Raziskovalni matematični seminar - Arhiv

In this talk, we will revisit the variety of antilattices and its connection with magic squares. This is work in progress with Karin Cvetko-Vah.

In matching theory it is a basic problem to determine all the edges in a given graph which can be extended to a maximum matching. Such edges are called maximally-matchable or allowed edges. In addition to its theoretical relevance this question has application in anonymity problems in databases and certain propagation methods in constraint programming. In the last years researchers from graph theory as well as from the above applications fields developed efficient polynomial time algorithms for the identification of allowed edges, but from practicalpo int of view only the bipartite solution is satisfactory for larger scale problems. While the bipartite case can be easily solved in linear time with respect to the number of edges, the complexity gap with the nonbipartite case is significant: a magnitude of the number of vertices.

In this talk first we will review the methods from the literature for determining the maximally-matchable edges. Then a decomposition theory based on the matching structure is presented with showing the related algorithmic concept for identifying the allowed edges. Finally we will show that a fixed-parameter linear time divide-and-conquer algorithm can be worked out for non-bipartite graphs, where the complexity of the new method will be expressed with the help of a graph parameter arising from the developed decomposition structure.

The talk is based on a joint work with Radoslaw Cymer (Augsburg).

The notion of density of a subgraph is usually defined as the number of edges in the subgraph divided by the number of its vertices. However, this definition is too permissive for the characterization of communities in graphs where each vertex should be densely connected within the community, with regard to its degree. Motivated by the idea of defining a notion of density more suitable for the study and identification of communities in graphs, we will be interested in the property of "proportional density". Specifically, we define a "proportionally dense subgraph" (PDS) as an induced subgraph such that each vertex in the PDS has proportionally more neighbors inside the PDS than in the whole graph. We will focus on the problem of finding a PDS of maximum size. Some hardness results on restricted classes of graphs will be presented (NP-hardness and APX-hardness), as well as a very simple polynomial-time 2-approximation algorithm. In the last part of the talk, we will give an upper bound on the size of a PDS in a graph based on its maximum degree and prove that all Hamiltonian cubic graphs have a PDS that reaches this bound.