The project 'Packing, covering and partitions of digraphs' is funded by the DKK 2,592,000 grant DFF-7014-00037A from the Independent Research Fund Denmark, Natural Sciences, running from January 1, 2018 through December 31, 2024.
The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark.

Participants

Environment

The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. The participants are all associated with the Research Training Programs in Mathematics and Computer Science as Ph.D. advisors.

Activities

Besides supervision of one postdoc, Thomas Bellitto, who was hired for 18 months starting in August 2018 and shorter terms postdocs Kristine Vitting Klinkby Knudsen and Yun Wang, the activities on this grant are research related traveling to conferences, meetings by invitation, research collaboration, and hosting guests.

Research visits and other external activities by members of the grant

2018

2019

2020

Due to Covid-19 most of our travelplans had to be cancelled.

2021

Again due to the Covid-19 situation we have had very little travel.

2022

2023

2024

Visits by collaborators

2018

2019

2020

Due to Covid-19 most of our planned visitors had to cancel their visit.

2021

Due to Covid-19 most of our planned visitors had to be canceled

2022

2023

2024

Meetings arranged or co-arranged by the group

Other events

Short Project description

The project deals with structural and algorithmic aspects of problems related to packing, coverings or partitions in digraphs and generalizations of digraphs such as edge-coloured graphs. Examples are: packing cycles, linkage problems, packing strong subdigraphs, branchings, vertex partitions with prescribed properties in (di)graphs, packing sub(di)graphs in digraphs, edge-coloured graphs, completing partial orientations of graphs to obtain digraphs with prescribed properties.

Publications

Here we list project related publications by members of the group since January 1, 2018.

Books and chapters in books

Classes of Directed Graphs.
Jørgen Bang-Jensen, Gregory Gutin (editors)
Springer Monographs in Mathematics, 2018.
Basic Terminology, Notation and Results.
Jørgen Bang-Jensen, Gregory Gutin
Chapter 1 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
Springer Monographs in Mathematics, 2018.
Tournaments and Semicomplete digraphs.
Jørgen Bang-Jensen, Frederic Havet
Chapter 2 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
Springer Monographs in Mathematics, 2018.
Locally Semicomplete digraphs and Generalizations.
Jørgen Bang-Jensen
Chapter 6 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
Springer Monographs in Mathematics, 2018.
Semicomplete Multipartite Digraphs.
Anders Yeo
Chapter 7 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
Springer Monographs in Mathematics, 2018.
Transversals in linear uniform hypergraphs.
Michael Henning and Anders Yeo
Springer (ISBN 978-3-030-46558-2) 2020.
Domination and Total Domination in Hypergraphs
Michael Henning and Anders Yeo
Chapter in "Structures of Domination in Graphs, Haynes, Hedetniemi and Henning (eds)
Volume 66 in Springer book series on Developments in Mathematics 2021

Peer-Reviewed International Journal Articles

Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs.
Michael A. Henning, Anders Yeo:
Discrete Mathematics 341(8): 2285-2292 (2018)
Degree constrained 2-partitions of semicomplete digraphs.
Jørgen Bang-Jensen, Tilde My Christiansen
Theoretical Computer Science 746: 112-123 (2018)
Out-degree reducing partitions of digraphs.
Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo.
Theoretical Computer Science 719: 64-72, 2018.

Chi-bounded families of oriented graphs.
Pierre Aboulker, Jørgen Bang-Jensen, Nicolas Bousquet, Pierre Charbit, Frédéric Havet, Frédéric Maffray, José Zamora.
Journal of Graph Theory 87: 285-304 (2018).

Completing orientations of partially oriented graphs.
Jørgen Bang-Jensen, Jing Huang, Xuding Zhu.
Journal of Graph Theory 87: 285-304, 2018.

Bipartite spanning sub(di)graphs induced by 2-partitions.
Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo.
Journal of Graph Theory 89: 304-326, 2018.

Tight lower bounds on the matching number in a graph with given maximum degree
Michael A. Henning and Anders Yeo.
Journal of Graph Theory 89: 115-149, 2018.

On upper transversals in 3-uniform hypergraphs
Michael A. Henning and Anders Yeo.
Electronic J. Combin. 25(4): P4.27, 2018.

Complexity of locally-injective homomorphisms to tournaments
Stefan Bard, Thomas Bellitto, Christopher Duffy, Gary MacGillivray, Feiran Yang.
Discrete Mathematics & Theoretical Computer Science
20(2) (2018)

Upper transversals in hypergraphs
Michael A. Henning and Anders Yeo.
Eur. J. Comb. 78 1-12 (2019)

Degree constrained 2-partitions of graphs.
Jørgen Bang-Jensen, Stéphane Bessy
Theoretical Computer Science 776: 64-74, 2019.

Bipartite spanning sub(di)graphs induced by 2‐partitions
Jørgen Bang-Jensen, Stéphane Bessy, Frederic Havet, Anders Yeo
Journal of Graph Theory 92: 130-151, 2019.

Strong subgraph k-connectivity
Yuefang Sun, Gregory Gutin, Anders Yeo and Xiaoyan Zhang
Journal of Graph Theory 92: 5-18, 2019.

The parameterized complexity landscape of finding 2-partitions of digraphs
Jørgen Bang-Jensen, Kristine Vitting Klinkby, Saket Saurabh, Meirav Zehavi
Theoretical Computer Science 795: 108-114, 2019.

Out-colourings of digraphs
Noga Alon, Jørgen Bang-Jensen, Stéphane Bessy
Journal of Graph Theory 93: 88-112, 2020.

On DP-colourings of digraphs
Jørgen Bang-Jensen, Thomas Bellitto, Thomas Schweser, Michael Stiebitz
Journal of Graph Theory 95: 76-98, 2020.

Hajos and Ore Constructions for Digraphs
Jørgen Bang-Jensen, Thomas Bellitto, Thomas Schweser, Michael Stiebitz
Electronic J. Combinatorics 27(1): P1.63, 2020.

The directed 2-linkage problem with length constraints
Jørgen Bang-Jensen, Thomas Bellitto, William Lochet, Anders Yeo.
Theoretical Computer Science 814: 69-73, 2020.

Bounds on upper transversals in hypergraphs
Michael A. Henning, Anders Yeo
J. Combinatorial Optimization39(1): 77-99, 2020.

Arc-disjoint strong spanning subdigraphs of semicomplete compositions
Jørgen Bang-Jensen, Gregory Gutin, Anders Yeo
Journal of Graph Theory95(2) 267-289 2020

Spanning eulerian subdigraphs avoiding k presecibed arcs in tournaments
Jørgen Bang-Jensen, Hugues Depres, Anders Yeo
Discrete Mathematics343(12) 112129 (2020).

On the parametrized complexity of 2-partitions
Jonas Bamse Andersen, Jørgen Bang-Jensen, Anders Yeo
Theoretical Computer Science 844: 69-73 (2020)

Proper‐walk connection number of graphs
Jørgen Bang-Jensen, Thomas Bellitto, Anders Yeo
Journal of Graph Theory96(1): 137-159 (2021)

Good orientations of unions of edge-disjoint spanning trees
Jørgen Bang-Jensen, Stephane Bessy, Jing Huang, Matthias Kriesell
Journal of Graph Theory 96: 594-618 (2021).

Affine Planes and Transversals in 3-Uniform Linear Hypergraphs
Michael A. Henning, Anders Yeo
Graphs and Combinatorics 37(3): 867-890 (2021).

Dominating vertex covers: the vertex-edge domination problem.
William Klostermeyer, Magaret-Ellen Messinger, Anders Yeo
Discuss. Math. Graph Theory 41(1) 123-132 (2021).

Matching and edge-connectivity in graphs with given maximum degree
Michael A. Henning, Anders Yeo
Discrete Math. 344(8) 112438 (2021).

On Supereulerian 2-edge coloured graphs
Jørgen Bang-Jensen, Thomas Bellitto, Anders Yeo
Graphs and Combinatorics 37(6) 2601-2620 (2021).

A new upper bound on the total domination number in graphs with minimum degree six
Michael Henning, Anders Yeo
Discrete Appl. Math. 302 1-7 (2021).

Lower bounds on Tuza constants for transversals in linear uniform hypergraphs
Michael Henning, Anders Yeo
Discrete Appl. Math. 304 12-22 (2021).

Component order connectivity in directed graphs
Jørgen Bang-Jensen, Eduard Eiben, Gregory Z. Gutin, Magnus Wahlström, Anders Yeo
Algorithmica 84(9) 2767-2784 (2022).

Every (13k - 6)-strong tournament with minimum out-degree at least 28k - 13 is k-linked
Jørgen Bang-Jensen, Kasper Skov Johansen
Discrete Mathematics 345(6) 112831 (2022).

Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
Jørgen Bang-Jensen, Frédéric Havet, Matthias Kriesell, Anders Yeo
J. Graph Theory 99(4) 615-636 (2022).

Arc-disjoint in- and out-branchings in digraphs of independence number at most 2.
Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo
J. Graph Theory 100(2) 294-314 (2022).

Good acyclic orientations of 4-regular 4-connected graphs
Jørgen Bang-Jensen, Matthias Kriesell
J. Graph Theory 100(4) 698-720 (2022).

Digraphs and Variable Degeneracy
Jørgen Bang-Jensen, Thomas Schweser, Michael Stiebitz
Siam J. Disc. Math 36(1) 578-595 (2022).

Complexity of some arc-partition problems for digraphs
Jørgen Bang-Jensen, Stéphane Bessy, Daniel Gonçalves, Lucas Picasarri-Arrieta
Theoretical Computer Science 928 167-182 (2022).

Low chromatics spanning sub(di)graphs with prescribed degree or connectivity properties
Jørgen Bang-Jensen, Fredderic Havet, matthias Kriesell, Anders Yeo
J. Graph Theory99 615-636 (2022).

Non-separating spanning trees and out-branchings in digraphs of independence number 2
Jørgen Bang-Jensen, Stéphane Bessy, Anders Yeo
Graphs Comb.38 187 (2022).

A complete description of convex sets associated with matchings and edge-connectivity in graphs
Michael Henning and Anders Yeo
J. Graph Theory101 643-667 (2022).

Complexity of (arc)-connectivity problems involving arc-reversals or deorientations
Jørgen Bang-Jensen, Florian Hoersch. Matthias Kriesell
Theor. Comput. Sci. 973 114097 (2023).

The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties
Jørgen Bang-Jensen, Anders Yeo
Theor. Comput. Sci949 113758 (2023).

Spanning eulerian subdigraphs in semicomplete digraphs
Jørgen Bang-Jensen, Frederic Havet, Anders Yeo
J. Graph Theory102 578-606 (2023).

Exact capacitated domination: On the computational complexity of uniqueness
Gregory Z. Gutin, Philip R. Neary, Anders Yeo
Discret. Appl. Math 332 155-169 (2023).

(1,1)-Cluster editing is polynomial-time solvable
Gregory Z. Gutin, Anders Yeo
Discret. Appl. Math 340 259-271 (2023).

Results on the small quasi-kernel conjecture
Jiangdong Ai, Stefanie Gerke, Gregory Z. Gutin, Anders Yeo, Yacong Zhou
Discret. Math. 346 113435 (2023).

k-best feature selection and ranking via stochastic approximation.
David V. Akman, Milad Malekipirbazari, Zeren D. Yenice, Anders Yeo, Niranjan Adhikari, Yong Kai Wong, Babak Abbasi, Alev Taskin Gumus
Expert Syst. Appl. 213 118864 (2023).

Unique Stable matchings
Gregory Z. Gutin, Philip R. Neary, Anders Yeo
Games Econ. Behav. 141 529-457 (2023).

Directed Steiner tree packing and directed tree connectivity
Yuefang Sun, Anders Yeo
J. Graph Theory 102 86-106 (2023).

Lower bounds for maximum weighted cut
Gregory Z. Gutin, Anders Yeo
Discret. Math. 1142-1161 (2023).

Preference swaps for the stable matching problem
Eduard Eiben, Gregory Z. Gutin, Philip R. Neary, Clément Rambaud, Magnus Wahlström, Anders Yeo
Theor. Comput. Sci. 940 222-230 (2023).

The Tuza-Vestergaard theorem
Michael A. Henning, Christian Löwenstein, Anders Yeo
SIAM J. Disc. Math. 37 1275-1310 (2023).

Constrained flows in networks
Jørgen Bang-Jensen, Stephane Bessy, Lucas Piccassari-Arrieta
Theor. Comput. Sci. 1010: 114702 (2024).

Arc-disjoint out- and in-branchings in compositions of digraphs
Jørgen Bang-Jensen, Yun Wang
Eur. J. Comb. 120: 103981 (2024).

Safe sets and in-dominating sets in digraphs
Yandong Bai, Jørgen Bang-Jensen, Shinya Fujita, Hirotaka Ono, Anders Yeo
Discret. Appl. Math. 346: 215-227 (2024).

Arc-disjoint out-branchings and in-branchings in semicomplete digraphs
Jørgen Bang-Jensen, Yun Wang
J. Graph Theory 106 (1) 182-197 (2024).

Edge-arc-disjoint paths in semicomplete mixed graphs
Jørgen Bang-Jensen, Yun Wang
J. Graph Theory online November 2024 https://doi.org/10.1002/jgt.23199
Note on disjoint cycles in multipartite tournaments
Gregory Z. Gutin, Wei Li, Shujing Wang, Anders Yeo, Yacong Zhou
Discret. Math. 347(10): 114126 (2024).
Finding all stable matchings with assignment constraints
Gregory Z. Gutin, Philip R. Neary, Anders Yeo
Games Econ. Behav. 148: 244-263 (2024).
On Seymour's and Sullivan's second neighbourhood conjectures
Jiangdong Ai, Stefanie Gerke, Gregory Z. Gutin, Shujing Wang, Anders Yeo, Yacong Zhou
J. Graph Theory 105(3): 413-426 (2024).
Transversals in regular uniform hypergraphs
Michael A. Henning, Anders Yeo
J. Graph Theory 105(3): 468-485 (2024).
Bounds on Maximum Weight Directed Cut
Jiangdong Ai, Stefanie Gerke, Gregory Z. Gutin, Anders Yeo,Yacong Zhou
SIAM J. Discret. Math. 38(3): 2370-2391 (2024).
The Parameterized Complexity of Guarding Almost Convex Polygons
Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
Discret. Comput. Geom. 71(2): 358-398 (2024).

Peer-Reviewed International Conference Articles


Parameterized Algorithms for Survivable Network Design with Uniform Demands.
Jørgen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi:
SODA: 2838-2850, SIAM, 2018.
[Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018.]

Component Order Connectivity in Directed Graphs
Jørgen Bang-Jensen, Eduard Eiben, Gregory Gutin, Magnus Wahlstrom and Anders Yeo,
IPEC 2020: 2:1-2:16 (2020)

Inversion number of an oriented graph and related parameters
Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, Frédéric Havet
ALGOS 2020 101-121 2020. dt>
Uniqueness of DP-Nash subgraphs and D-sets in weighted graphs of Netflix games
Gregory Gutin, Philip Neary Anders Yeo
COCOON 2020360-371 (2020)

k-Distinct Branchings Admits a Polynomial Kernel
Jørgen Bang-Jensen, Kristine Vitting Klinkby Knudsen, Saket Saurabh,
ESA 2021 11.1-11.15 2021.

Strong Connectivity Augmentation is FPT
Kristine Vitting Klinkby, Pranabendu Misra, Saket Saurabh.
SODA: 219-234, SIAM, 2021.

Perfect forests and their extensions
Gregory Gutin, Anders Yeo
MFCS 2021:54:1-54:13, 2021

Complexity of efficient outsomes in binary-auction polymatrix games with implications for coordination problems
Argyrios Deligkas, Eduard Eiben, Gregory Gutin, Philip Neary, Anders Yeo.
IJCAI: 2023.

A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands.
Jørgen Bang-Jensen, Kristine Vitting Klinkby Knudsen, Pranabendu Misra, Saket Saurabh,
ESA 2023 13.1-13.15 2023.