Source author record

J. Bang-Jensen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms math.CO

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Component Order Connectivity in Directed Graphs

A directed graph $D$ is semicomplete if for every pair $x,y$ of vertices of $D,$ there is at least one arc between $x$ and $y.$ \viol{Thus, a tournament is a semicomplete digraph.} In the Directed Component Order Connectivity (DCOC) problem, given a digraph $D=(V,A)$ and a pair of natural numbers $k$ and $\ell$ , we are to decide whether there is a subset $X$ of $V$ of size $k$ such that the largest strong connectivity component in $D-X$ has at most $\ell$ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for $\ell=1.$ We study parametered complexity of DCOC for general and semicomplete digraphs with the following parameters: $k, \ell,\ell+k$ and $n-\ell$ . In particular, we prove that DCOC with parameter $k$ on semicomplete digraphs can be solved in time $O^*(2^{16k})$ but not in time $O^*(2^{o(k)})$ unless the Exponential Time Hypothesis (ETH) fails. \gutin{The upper bound $O^*(2^{16k})$ implies the upper bound $O^*(2^{16(n-\ell)})$ for the parameter $n-\ell.$ We complement the latter by showing that there is no algorithm of time complexity $O^*(2^{o({n-\ell})})$ unless ETH fails.} Finally, we improve \viol{(in dependency on $\ell$ )} the upper bound of G{ö}ke, Marx and Mnich (2019) for the time complexity of DCOC with parameter $\ell+k$ on general digraphs from $O^*(2^{O(k\ell\log (k\ell))})$ to $O^*(2^{O(k\log (k\ell))}).$ Note that Drange, Dregi and van 't Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time $O^*(2^{o(k\log \ell)})$ unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity $O^*(2^{o(k\log k)}).$

preprint2020arXiv

Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties

Generalizing well-known results of Erdős and Lovász, we show that every graph $G$ contains a spanning $k$ -partite subgraph $H$ with $λ(H)\geq \lceil{}\frac{k-1}{k}λ(G)\rceil$ , where $λ(G)$ is the edge-connectivity of $G$ . In particular, together with a well-known result due to Nash-Williams and Tutte, this implies that every $7$ -edge-connected graphs contains a spanning bipartite graph whose edge set decomposes into two edge-disjoint spanning trees. We show that this is best possible as it does not hold for infintely many $6$ -edge-connected graphs. For directed graphs, it was shown in [6] that there is no $k$ such that every $k$ -arc-connected digraph has a spanning strong bipartite subdigraph. We prove that every strong digraph has a spanning strong 3-partite subdigraph and that every strong semicomplete digraph on at least 6 vertices contains a spanning strong bipartite subdigraph. \jbj{We generalize this result to higher connectivities by proving} that, for every positive integer $k$ , every $k$ -arc-connected digraph contains a spanning $(2k+1$ )-partite subdigraph which is $k$ -arc-connected and this is best possible. A conjecture in [18] implies that every digraph of minimum out-degree $2k-1$ contains a spanning $3$ -partite subdigraph with minimum out-degree at least $k$ . We prove that the bound $2k-1$ would be best possible by providing an infinite class of digraphs with minimum out-degree $2k-2$ which do not contain any spanning $3$ -partite subdigraph in which all out-degrees are at least $k$ . We also prove that every digraph of minimum semi-degree at least $3r$ contains a spanning $6$ -partite subdigraph in which every vertex has in- and out-degree at least $r$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.