Source author record

Hugo Jacob

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 Discrete Mathematics math.CO

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs

Twin-width is a newly introduced graph width parameter that aims at generalizing a wide range of "nicely structured" graph classes. In this work, we focus on obtaining good bounds on twin-width $\text{tww}(G)$ for graphs $G$ from a number of classic graph classes. We prove the following: - $\text{tww}(G) \leq 3\cdot 2^{\text{tw}(G)-1}$ , where $\text{tw}(G)$ is the treewidth of $G$ , - $\text{tww}(G) \leq \max(4\text{bw}(G),\frac{9}{2}\text{bw}(G)-3)$ for a planar graph $G$ with $\text{bw}(G) \geq 2$ , where $\text{bw}(G)$ is the branchwidth of $G$ , - $\text{tww}(G) \leq 183$ for a planar graph $G$ , - the twin-width of a universal bipartite graph $(X,2^X,E)$ with $|X|=n$ is $n - \log_2(n) + \mathcal{O}(1)$ . An important idea behind the bounds for planar graphs is to use an embedding of the graph and sphere-cut decompositions to obtain good bounds on neighbourhood complexity.

preprint2022arXiv

List Colouring Trees in Logarithmic Space

We show that List Colouring can be solved on $n$ -vertex trees by a deterministic Turing machine using $O(\log n)$ bits on the worktape. Given an $n$ -vertex graph $G=(V,E)$ and a list $L(v)\subseteq\{1,\dots,n\}$ of available colours for each $v\in V$ , a list colouring for $G$ is a proper colouring $c$ such that $c(v)\in L(v)$ for all $v$ .

preprint2022arXiv

XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure

In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing $W[1]$ -hardness proofs for these problems, since XNLP-hardness implies $W[t]$ -hardness for all $t$ . It also indicates, via a conjecture by Pilipczuk and Wrochna [ToCT 2018], that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, ( $q$ -)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, and Bipartite Bandwidth.

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.

Hugo Jacob

Research overview

Is this your work?

3 publications

Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs

List Colouring Trees in Logarithmic Space

XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure

See the researcher in context

Building this map preview