Source author record

Peter Gartland

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

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Finding large induced sparse subgraphs in $C_{>t}$ -free graphs in quasipolynomial time

For an integer $t$ , a graph $G$ is called {\em{ $C_{>t}$ -free}} if $G$ does not contain any induced cycle on more than~ $t$ vertices. We prove the following statement: for every pair of integers $d$ and $t$ and a CMSO $_2$ statement~ $ϕ$ , there exists an algorithm that, given an $n$ -vertex $C_{>t}$ -free graph $G$ with weights on vertices, finds in time $n^{O(\log^4 n)}$ a maximum-weight vertex subset $S$ such that $G[S]$ has degeneracy at most $d$ and satisfies $ϕ$ . The running time can be improved to $n^{O(\log^2 n)}$ assuming $G$ is $P_t$ -free, that is, $G$ does not contain an induced path on $t$ vertices. This expands the recent results of the authors [to appear at FOCS 2020 and SOSA 2021] on the {\sc{Maximum Weight Independent Set}} problem on $P_t$ -free graphs in two directions: by encompassing the more general setting of $C_{>t}$ -free graphs, and by being applicable to a much wider variety of problems, such as {\sc{Maximum Weight Induced Forest}} or {\sc{Maximum Weight Induced Planar Graph}}.

preprint2020arXiv

Dominated Minimal Separators are Tame (Nearly All Others are Feral)

A class ${\cal F}$ of graphs is called {\em tame} if there exists a constant $k$ so that every graph in ${\cal F}$ on $n$ vertices contains at most $O(n^k)$ minimal separators, {\em strongly-quasi-tame} if every graph in ${\cal F}$ on $n$ vertices contains at most $O(n^{k \log n})$ minimal separators, and {\em feral} if there exists a constant $c > 1$ so that ${\cal F}$ contains $n$ -vertex graphs with at least $c^n$ minimal separators for arbitrarily large $n$ . The classification of graph classes into tame or feral has numerous algorithmic consequences, and has recently received considerable attention. A key graph-theoretic object in the quest for such a classification is the notion of a $k$ -{\em creature}. In a recent manuscript [Abrishami et al., Arxiv 2020] conjecture that every hereditary class ${\cal F}$ that excludes $k$ -creatures for some fixed constant $k$ is tame. We give a counterexample to this conjecture and prove the weaker result that a hereditary class ${\cal F}$ is strongly quasi-tame if it excludes $k$ -creatures for some fixed constant $k$ and additionally every minimal separator can be dominated by another fixed constant $k'$ number of vertices. The tools developed also lead to a number of additional results of independent interest. {\bf (i) We obtain a complete classification of all hereditary graph classes defined by a finite set of forbidden induced subgraphs into strongly quasi-tame or feral. This generalizes Milanič and Pivač [WG'19]. {\bf (ii)} We show that hereditary class that excludes $k$ -creatures and additionally excludes all cycles of length at least $c$ , for some constant $c$ , are tame. This generalizes the result of [Chudnovsky et al., Arxiv 2019]. {\bf (iii)} We show that every hereditary class that excludes $k$ -creatures and additionally excludes a complete graph on $c$ vertices for some fixed constant $c$ is tame.

preprint2020arXiv

Independent Set on P $_k$ -Free Graphs in Quasi-Polynomial Time

We present an algorithm that takes as input a graph $G$ with weights on the vertices, and computes a maximum weight independent set $S$ of $G$ . If the input graph $G$ excludes a path $P_k$ on $k$ vertices as an induced subgraph, the algorithm runs in time $n^{O(k^2 \log^3 n)}$ . Hence, for every fixed $k$ our algorithm runs in quasi-polynomial time. This resolves in the affirmative an open problem of [Thomassé, SODA'20 invited presentation]. Previous to this work, polynomial time algorithms were only known for $P_4$ -free graphs [Corneil et al., DAM'81], $P_5$ -free graphs [Lokshtanov et al., SODA'14], and $P_6$ -free graphs [Grzesik et al., SODA'19]. For larger values of $t$ , only $2^{O(\sqrt{kn\log n})}$ time algorithms [Bascó et al., Algorithmica'19] and quasi-polynomial time approximation schemes [Chudnovsky et al., SODA'20] were known. Thus, our work is the first to offer conclusive evidence that Independent Set on $P_k$ -free graphs is not NP-complete for any integer $k$ . Additionally we show that for every graph $H$ , if there exists a quasi-polynomial time algorithm for Independent Set on $C$ -free graphs for every connected component $C$ of $H$ , then there also exists a quasi-polynomial time algorithm for {\sc Independent Set} on $H$ -free graphs. This lifts our quasi-polynomial time algorithm to $T_k$ -free graphs, where $T_k$ has one component that is a $P_k$ , and $k-1$ components isomorphic to a fork (the unique $5$ -vertex tree with a degree $3$ vertex).

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.

Peter Gartland

Research overview

Is this your work?

3 publications

Finding large induced sparse subgraphs in $C_{>t}$ -free graphs in quasipolynomial time

Dominated Minimal Separators are Tame (Nearly All Others are Feral)

Independent Set on P $_k$ -Free Graphs in Quasi-Polynomial Time

See the researcher in context

Building this map preview

Peter Gartland

Research overview

Is this your work?

3 publications

Finding large induced sparse subgraphs in C>tC_{>t}C>t​-free graphs in quasipolynomial time

Dominated Minimal Separators are Tame (Nearly All Others are Feral)

Independent Set on Pk_kk​-Free Graphs in Quasi-Polynomial Time

See the researcher in context

Building this map preview

Finding large induced sparse subgraphs in $C_{>t}$ -free graphs in quasipolynomial time

Independent Set on P $_k$ -Free Graphs in Quasi-Polynomial Time