English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we investigate the existence of subexponential parameterizedalgorithms of three fundamental cycle-hitting problems in geometric graphclasses. The considered problems, \textsc{Triangle Hitting} (TH),\textsc{Feedback Vertex Set} (FVS), and \textsc{Odd Cycle Transversal} (OCT)ask for the existence in a graph $G$ of a set $X$ of at most $k$ vertices suchthat $G-X$ is, respectively, triangle-free, acyclic, or bipartite. Suchsubexponential parameterized algorithms are known to exist in planar and even$H$-minor free graphs from bidimensionality theory [Demaine et al., JACM 2005],and there is a recent line of work lifting these results to geometric graphclasses consisting of intersection of "fat" objects ([Grigoriev et al., FOCS2022] and [Lokshtanov et al., SODA 2022]). In this paper we focus on "thin"objects by considering intersection graphs of segments in the plane with $d$possible slopes ($d$-DIR graphs) and contact graphs of segments in the plane.Assuming the ETH, we rule out the existence of algorithms:  - solving TH in time $2^{o(n)}$ in 2-DIR graphs; and  - solving TH, FVS, and OCT in time $2^{o(\sqrt{n})}$ in $K_{2,2}$-freecontact 2-DIR graphs.  These results indicate that additional restrictions are necessary in order toobtain subexponential parameterized algorithms for %these problems. In thisdirection we provide:  - a $2^{O(k^{3/4}\cdot \log k)}n^{O(1)}$-time algorithm for FVS in contactsegment graphs;  - a $2^{O(\sqrt d\cdot t^2 \log t\cdot k^{2/3}\log k)} n^{O(1)}$-timealgorithm for TH in $K_{t,t}$-free $d$-DIR graphs; and  - a $2^{O(k^{7/9}\log^{3/2}k)} n^{O(1)}$-time algorithm for TH in contactsegment graphs.

Subexponential parameterized algorithms for cycle-hitting problems in contact and intersection graphs of segments