Equitable partitions into matchings and coverings in mixed graphs

DOI10.1016/J.DISC.2021.112651MaRDI QIDQ2237227zbMATH OpenOpenAlexFDO

Publication date 27 October 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.07856

edge cover matching mixed graph partitioning problem

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Integer programming (90C10) Combinatorial optimization (90C27)

Abstract: Matchings and coverings are central topics in graph theory. The close relationship between these two has been key to many fundamental algorithmic and polyhedral results. For mixed graphs, the notion of matching forest was proposed as a common generalization of matchings and branchings. In this paper, we propose the notion of mixed edge cover as a covering counterpart of matching forest, and extend the matching--covering framework to mixed graphs. While algorithmic and polyhedral results extend fairly easily, partition problems are considerably more difficult in the mixed case. We address the problems of partitioning a mixed graph into matching forests or mixed edge covers, so that all parts are equal with respect to some criterion, such as edge/arc numbers or total sizes. Moreover, we provide the best possible multicriteria equalization.

Review text

A mixed graph \(G = (V, E, A)\) consists of a set of undirected edges \(E\), and a set of directed arcs \(A\), living in the same vertex set \(V\). (In mixed graphs, the authors consider undirected edges to have both directions where necessary.) The authors consider generalisations of the notion of edge covers in graphs in the setting of mixed graphs. The two main notions considered read as follows. \par i) Given a mixed graph \(G = (V,E,A)\), a mixed edge cover \(F \subseteq E \cup A\) is such that for every \(v \in V\) there is a directed path in \(F \cap A\) starting from some endpoint of an edge in \(F \cap E\), and ending in \(v\). \par ii) A mixed covering forest \(F \subseteq E \cup A\) is such that the underlying undirected graph formed by \(F\) is acyclic and every vertex is covered at least once by \(F\) (meaning, is the endpoint of some edge in \(F\), recalling undirected edges are assumed to have both endpoints). The authors mainly consider problems of partitioning the edge-arc set of mixed graphs into ``almost-equitable mixed edge covers or mixed covering forests, for various notions of what it means to be almost-equitable. For instance, one of their results is the following. If \(G = (V,E,A)\) is a mixed graph that can be partitioned into \(k\) mixed matching forests, then \(G\) can be partitioned into \(k\) matching forests \(F_1, \dotsc, F_k\) in such a way that for every \(1 \leq i\), \(j \leq k\), we have \(||F_i|-|F_j|| \leq 1\), \(||F_i \cap A|-|F_j \cap A|| \leq 2\), and \(||F_i \cap E| - |F_j \cap E|| \leq 2\). En route to these partitioning results, the authors also prove various combinatorial, algorithmic and polyhedral results concerning mixed matching forests and mixed edge covers.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Equitable partitions into matchings and coverings in mixed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2237227)