### Book chapter

## Faster algorithms for half-integral T -Path packing

Let G = (V,E) be an undirected graph, T ⊆ V be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O ( m √n log n 2 /m log n ) -Time algorithm (hereinafter n := |V |, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2 , 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O ( m √n log n 2 /m log n )time, thus matching the complexities of integral and half-integral versions.

### In book

The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite graphs, matchings, Petri nets, planar graphs, transport nets). Some algorithms often used in practice on graphs are given. It is considered classical combinatorial configurations and their generating functions, recurrent sequences. It is put in a basis of the book long-term experience of teaching by authors the discipline «Discrete mathematics» at the business informatics faculty, at the computer science faculty* *of National Research University Higher School of Economics, and at the automatics and computer technique faculty of National research university Moscow power engineering institute. The book is intended for the students of a bachelor degree, trained at the computer science faculties in the directions 09.03.01 Informatics and computational technique, 09.03.02 Informational systems and technologies, 09.03.03 Applied informatics, 09.03.04 Software Engineering, and also for IT experts and developers of software products.

We consider an undirected graph $G = (VG, EG)$ with a set $T \subseteq VG$ of terminals, and with nonnegative integer capacities $c(v)$ and costs $a(v)$ of nodes $v\in VG$. A path in $G$ is a \emph{$T$-path} if its ends are distinct terminals. By a \emph{multiflow} we mean a function $F$ assigning to each $T$-path $P$ a nonnegative rational \emph{weight} $F(P)$, and a multiflow is called \emph{feasible} if the sum of weights of $T$-paths through each node $v$ does not exceed $c(v)$. The emph{value} of $F$ is the sum of weights $F(P)$, and the \emph{cost} of $F$ is the sum of $F(P)$ times the cost of $P$ w.r.t. $a$, over all $T$-paths $P$. Generalizing known results on edge-capacitated multiflows, we show that the problem of finding a minimum cost multiflow among the feasible multiflows of maximum possible value admits \emph{half-integer} optimal primal and dual solutions. Moreover, we devise a strongly polynomial algorithm for finding such optimal solutions.

Given a digraph $G = (VG,AG)$, an even factor $M \subseteq AG$ is a set formed by node-disjoint paths and even cycles. Even factors in digraphs were introduced by Geelen and Cunningham and generalize path matchings in undirected graphs. Finding an even factor of maximum cardinality in a general digraph is known to be NP-hard but for the class of odd-cycle symmetric digraphs the problem is polynomially solvable. So far the only combinatorial algorithm known for this task is due to Pap; its running time is $O(n^4)$ (hereinafter $n$ denotes the number of nodes in $G$ and $m$ denotes the number of arcs or edges). In this paper we introduce a novel sparse recovery technique and devise an $O(n^3 \log n)$-time algorithm for finding a maximum cardinality even factor in an odd-cycle symmetric digraph. Our technique also applies to other similar problems, e.g. finding a maximum cardinality square-free simple $b$-matching.

In Russia from 2009 College admission is based on results of Unified State Exam. Entrant applies to no more than five universities. Admission mechanism is defined by government for all state universities. In the paper the authors model how entrant chooses university for application and, based on the entrant's choice prediction, the shortages of the current admission mechanism are revealed.

Matching problem with preferences being simplest semiorders is analysed. It is proved that a stable matching always exists. Furthermore, for any stable matching there exists a linear extension of preferences, which does not sontradict stability of a matching. In the college admission problem common goal is to find student-optimal stable matching. We provide a simple criteria (Stable Improvement Cycle existence), that allows to check, whether some particular stable matching is student-side Pareto optimal.

The goal of the expert search task is nding knowledgeable persons within the enterprise. In this paper we focus on its distinctions from the other information retrieval tasks. We review the existing approaches and propose a new term weighting scheme which is based on analysis of communication patterns between people. The eectiveness of the proposed approach is evaluated on a collection of e-mails from an organization of approximately 1500 people. Results show that it is possible to take into account communication structure in the process of term weighting, eectively combining communication-based and document-based approaches to expert finding.

This book constitutes the refereed post-conference proceedings of the 29th International Workshop on Combinatorial Algorithms, IWOCA 2018, held in Singapore, Singapore, in July 2018. The 31 regular papers presented in this volume were carefully reviewed and selected from 69 submissions. They cover diverse areas of combinatorical algorithms, complexity theory, graph theory and combinatorics, combinatorial optimization, cryptography and information security, algorithms on strings and graphs, graph drawing and labelling, computational algebra and geometry, computational biology, probabilistic and randomised algorithms, algorithms for big data analytics, and new paradigms of computation.