Search

Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Pre-assignment for Uniquification of Minimum Vertex Cover problem (shortly PAU-VC) is the problem, for given a graph $G$, to find a minimum set $S$ of vertices in $G$ such that there is a unique minimum vertex cover of $G$ containing $S$. We show that PAU-VC is fixed-parameter tractable parameterized by clique-width, which improves an exponential algorithm for trees given by Horiyama et al. Among natural graph classes with unbounded clique-width, we show that the problem can be solved in linear time on split graphs and unit interval graphs., Comment: 19 pages, 3 figures

An \emph{induced packing} of cycles in a graph is a set of vertex-disjoint cycles with no edges between them. We generalise the classic Erd\H{o}s-P\'osa theorem to induced packings of cycles. More specifically, we show that there exists a function ${f(k) = \mathcal{O}(k \log k)}$ such that for every positive integer ${k}$, every graph $G$ contains either an induced packing of $k$ cycles or a set $X$ of at most~${f(k)}$ vertices such that the closed neighbourhood of $X$ intersects all cycles in $G$. Our proof is constructive and yields a polynomial-time algorithm finding either the induced packing of cycles or the set $X$. Furthermore, we show that for every positive integer ${d}$, if a graph $G$ does not contain two cycles at distance more than $d$, then $G$ contains sets $X_1,X_2\subseteq V(G)$ with $\lvert {X_1} \rvert \leq12(d+1)$ and $\lvert {X_2} \rvert \leq12$ such that after removing the ball of radius $2d$ around $X_1$ or the ball of radius $3d$ around $X_2$, the resulting graphs are forests. As a corollary, we prove that every graph with no $K_{1,t}$ induced subgraph and no induced packing of $k$ cycles has tree-independence number at most $\mathcal{O}(tk\log k)$, and one can construct a corresponding tree-decomposition in polynomial time. This resolves a special case of a conjecture of Dallard et al. (arXiv:2402.11222), and implies that on such graphs, many NP-hard problems, such as Maximum Weight Independent Set, Maximum Weight Induced Matching, Graph Homomorphism, and Minimum Weight Feedback Vertex Set, are solvable in polynomial time. On the other hand, we show that the class of all graphs with no $K_{1,3}$ induced subgraph and no two cycles at distance more than $2$ has unbounded tree-independence number., Comment: 27 pages, 3 figures

Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes defined by finitely many forbidden induced subgraphs. Their result also implies a characterization of graph classes defined by finitely many forbidden induced subgraphs that are $(tw,\omega)$-bounded, that is, treewidth can only be large due to the presence of a large clique. This condition is known to be satisfied for any graph class with bounded tree-independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milani\v{c}, and \v{S}torgel in 2024. Dallard et al. conjectured that $(tw,\omega)$-boundedness is actually equivalent to bounded tree-independence number. We address this conjecture in the context of graph classes defined by finitely many forbidden induced subgraphs and prove it for the case of graph classes excluding an induced star. We also prove it for subclasses of the class of line graphs, determine the exact values of the tree-independence numbers of line graphs of complete graphs and line graphs of complete bipartite graphs, and characterize the tree-independence number of $P_4$-free graphs, which implies a linear-time algorithm for its computation. Applying the algorithmic framework provided in a previous paper of the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes., Comment: 26 pages

In this work, we propose and assess the potential of generative artificial intelligence (AI) to generate public engagement around potential clean energy sources. Such an application could increase energy literacy -- an awareness of low-carbon energy sources among the public therefore leading to increased participation in decision-making about the future of energy systems. We explore the use of generative AI to communicate technical information about low-carbon energy sources to the general public, specifically in the realm of nuclear energy. We explored 20 AI-powered text-to-image generators and compared their individual performances on general and scientific nuclear-related prompts. Of these models, DALL-E, DreamStudio, and Craiyon demonstrated promising performance in generating relevant images from general-level text related to nuclear topics. However, these models fall short in three crucial ways: (1) they fail to accurately represent technical details of energy systems; (2) they reproduce existing biases surrounding gender and work in the energy sector; and (3) they fail to accurately represent indigenous landscapes -- which have historically been sites of resource extraction and waste deposition for energy industries. This work is performed to motivate the development of specialized generative tools and their captions to improve energy literacy and effectively engage the public with low-carbon energy sources., Comment: 26 pages, 11 figures, 9 tables, submitted to review

A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. Pivot-minors have mainly been studied from a structural perspective. In this paper we perform the first systematic computational complexity study of pivot-minors. We first prove that the Pivot-Minor problem, which asks if a given graph $G$ contains a pivot-minor isomorphic to a given graph $H$, is NP-complete. If $H$ is not part of the input, we denote the problem by $H$-Pivot-Minor. We give a certifying polynomial-time algorithm for $H$-Pivot-Minor when (1) $H$ is an induced subgraph of $P_3+tP_1$ for some integer $t\geq 0$, (2) $H=K_{1,t}$ for some integer $t\geq 1$, or (3) $|V(H)|\leq 4$ except when $H \in \{K_4,C_3+ P_1\}$. Let ${\cal F}_H$ be the set of induced-subgraph-minimal graphs that contain a pivot-minor isomorphic to $H$. To prove the above statement, we either show that there is an integer $c_H$ such that all graphs in ${\cal F}_H$ have at most $c_H$ vertices, or we determine ${\cal F}_H$ precisely, for each of the above cases., Comment: 33 pages, 9 figures. An extended abstract appeared in the proceedings of WG2018

We study spontaneous supersymmetry breaking in inhomogeneous extensions of ${\cal N}=1$ supersymmetric field theory models in 4-dimensions. The ${\cal N}=1$ Abelian Higgs model with the inhomogeneous mass parameter and the FI coefficient that are dependent on spatial coordinates, as well as the O'Raifeartaigh model with all its parameters being dependent on spatial coordinates, are studied in detail. In the presence of inhomogeneous parameters, half supersymmetry can be preserved by adding appropriate inhomogeneous deformations to the original Lagrangians. The inhomogeneous deformations often break the R-symmetry explicitly. In cases where the inhomogeneous deformations do not break the R-symmetry explicitly, we demonstrate that spontaneous breaking of the R-symmetry is infeasible. We argue that those models can not be spontaneous supersymmetry breaking models, according to the Nelson-Seiberg argument. We comment on this issue in the context of a generic ${\cal N}=1$ supersymmetric model as well., Comment: 25 pages, no figures

AI alignment refers to models acting towards human-intended goals, preferences, or ethical principles. Given that most large-scale deep learning models act as black boxes and cannot be manually controlled, analyzing the similarity between models and humans can be a proxy measure for ensuring AI safety. In this paper, we focus on the models' visual perception alignment with humans, further referred to as AI-human visual alignment. Specifically, we propose a new dataset for measuring AI-human visual alignment in terms of image classification, a fundamental task in machine perception. In order to evaluate AI-human visual alignment, a dataset should encompass samples with various scenarios that may arise in the real world and have gold human perception labels. Our dataset consists of three groups of samples, namely Must-Act (i.e., Must-Classify), Must-Abstain, and Uncertain, based on the quantity and clarity of visual information in an image and further divided into eight categories. All samples have a gold human perception label; even Uncertain (severely blurry) sample labels were obtained via crowd-sourcing. The validity of our dataset is verified by sampling theory, statistical theories related to survey design, and experts in the related fields. Using our dataset, we analyze the visual alignment and reliability of five popular visual perception models and seven abstention methods. Our code and data is available at https://github.com/jiyounglee-0523/VisAlign., Comment: Published as a conference paper at NeurIPS 2023 (Track on Datasets and Benchmarks)

In this paper, we consider a variant of dichromatic number on digraphs with prescribed sets of arcs. Let $D$ be a digraph and let $Z_1, Z_2$ be two sets of arcs in $D$. For a subdigraph $H$ of $D$, let $A(H)$ denote the set of all arcs of $H$. Let $\mu(D, Z_1, Z_2)$ be the minimum number of parts in a vertex partition $\mathcal{P}$ of $D$ such that for every $X\in \mathcal{P}$, the subdigraph of $D$ induced by $X$ contains no directed cycle $C$ with $|A(C)\cap Z_1|\neq |A(C)\cap Z_2|$. For $Z_1=A(D)$ and $Z_2=\emptyset$, $\mu(D, Z_1, Z_2)$ is equal to the dichromatic number of $D$. We prove that for every digraph $F$ and every tuple $(a_e,b_e,r_e, q_e)$ of integers with $q_e\ge 2$ and $\gcd(a_e,q_e)=\gcd(b_e,q_e)=1$ for each arc $e$ of $F$, there exists an integer $N$ such that if $\mu(D, Z_1, Z_2)\ge N$, then $D$ contains a subdigraph isomorphic to a subdivision of $F$ in which each arc $e$ of $F$ is subdivided into a directed path~$P_e$ such that~$a_e|A(P_e)\cap Z_1|+b_e|A(P_e)\cap Z_2|\equiv {r_e}\pmod {q_e}$. This generalizes a theorem of Steiner [Subdivisions with congruence constraints in digraphs of large chromatic number, arXiv:2208.06358] which corresponds to the case when $(a_e, b_e, Z_1, Z_2)=(1, 1, A(D), \emptyset)$., Comment: 13 pages, 2 figures

The $r$-flip-width of a graph, for $r\in \mathbb{N}\cup \{\infty\}$, is a graph parameter defined in terms of a variant of the cops and robber game, called a flipper game, and it was introduced by Toru\'{n}czyk [Flip-width: Cops and robber on dense graphs, FOCS 2023]. We prove that for every $r\in (\mathbb{N}\setminus \{1\})\cup \{\infty\}$, the class of graphs of $r$-flip-width at most $2$ is exactly the class of ($C_5$, bull, gem, co-gem)-free graphs, which are known as totally decomposable graphs with respect to bi-joins., Comment: 13 pages, 3 figures

Particle physics today faces the challenge of explaining the mystery of dark matter, the origin of matter over anti-matter in the Universe, the origin of the neutrino masses, the apparent fine-tuning of the electro-weak scale, and many other aspects of fundamental physics. Perhaps the most striking frontier to emerge in the search for answers involves new physics at mass scales comparable to familiar matter, below the GeV-scale, or even radically below, down to sub-eV scales, and with very feeble interaction strength. New theoretical ideas to address dark matter and other fundamental questions predict such feebly interacting particles (FIPs) at these scales, and indeed, existing data provide numerous hints for such possibility. A vibrant experimental program to discover such physics is under way, guided by a systematic theoretical approach firmly grounded on the underlying principles of the Standard Model. This document represents the report of the FIPs 2022 workshop, held at CERN between the 17 and 21 October 2022 and aims to give an overview of these efforts, their motivations, and the decadal goals that animate the community involved in the search for FIPs., Comment: 383 pp, 176 figures

We introduce the vertex-arboricity of group-labelled graphs. For an abelian group $\Gamma$, a $\Gamma$-labelled graph is a graph whose edges are labelled by elements of $\Gamma$. For an abelian group $\Gamma$ and $A\subseteq \Gamma$, the $(\Gamma, A)$-vertex-arboricity of a $\Gamma$-labelled graph is the minimum integer $k$ such that its vertex set can be partitioned into $k$ parts where each part induces a subgraph having no cycle of value in $A$. We prove that for every positive integer $\omega$, there is a function $f_{\omega}:\mathbb{N}\times\mathbb{N}\to \mathbb{R}$ such that if $|\Gamma\setminus A|\le \omega$, then every $\Gamma$-labelled graph with $(\Gamma, A)$-vertex-arboricity at least $f_{\omega}(t,d)$ contains a subdivision of $K_t$ where all branching paths are of value in $A$ and of length at least $d$. This extends a well-known result that every graph of sufficiently large chromatic number contains a subdivision of $K_t$, in various directions., Comment: 15 pages, 1 figure

We introduce graph width parameters, called $\alpha$-edge-crossing width and edge-crossing width. These are defined in terms of the number of edges crossing a bag of a tree-cut decomposition. They are motivated by edge-cut width, recently introduced by Brand et al. (WG 2022). We show that edge-crossing width is equivalent to the known parameter tree-partition-width. On the other hand, $\alpha$-edge-crossing width is a new parameter; tree-cut width and $\alpha$-edge-crossing width are incomparable, and they both lie between tree-partition-width and edge-cut width. We provide an algorithm that, for a given $n$-vertex graph $G$ and integers $k$ and $\alpha$, in time $2^{O((\alpha+k)\log (\alpha+k))}n^2$ either outputs a tree-cut decomposition certifying that the $\alpha$-edge-crossing width of $G$ is at most $2\alpha^2+5k$ or confirms that the $\alpha$-edge-crossing width of $G$ is more than $k$. As applications, for every fixed $\alpha$, we obtain FPT algorithms for the List Coloring and Precoloring Extension problems parameterized by $\alpha$-edge-crossing width. They were known to be W[1]-hard parameterized by tree-partition-width, and FPT parameterized by edge-cut width, and we close the complexity gap between these two parameters., Comment: 26 pages, 1 figure, accepted to WG2023

We find a $(1+1)$-dimensional metric solution for a background hosting various supersymmetric field theories with a single non-chiral real supercharge. This supersymmetric background is globally hyperbolic even though it contains a naked null singularity. In this regard, we show that scalar wave propagation on the background is well-defined and so the curvature singularity is a {\it mild} one. Taking inspiration from our previous work, we relate the field theory on this curved background to some classes of $(1+1)$-dimensional inhomogeneous field theory in the supersymmetric setup. Utilizing our supersymmetric background, we elucidate the limitations of canonical quantization and highlight the conceptual advantages of the algebraic approach to quantization., Comment: V1: 1+46 pages, 10 figures. V2: Minor typos fixed, V3: Added some references with major improvement, 1+48 pages,V4: Minor corrections, Published version, 1+50 pages

Since its first demonstration in 1995, terahertz time-domain imaging has attracted an increasingly growing interest for its ability to reveal spectral fingerprints of materials, probe changes in refractive index and absorption, as well as detect the inner structure of complex objects via time-of-flight measurements. Practically, however, its widespread use has been hampered by the very long acquisition time typically required to spatially raster-scan the object and, for each spatial point, record the field in time via a delay line. Here, we address this fundamental bottleneck by implementing a scanless single-pixel imaging scheme, which sets the path for an unprecedented reduction of both system complexity and acquisition time. By properly exploiting natural wave diffraction, time-to-space encoding applied to terahertz point detection allows for an almost instantaneous capture of the terahertz waveforms, while multidimensional images are reconstructed via a computational approach. Our scheme is a promising solution for the development of next-generation fast and compact terahertz imagers perfectly suitable for high-repetition-rate laser sources., Comment: 18 pages, 5 figures

In 1965, Erd\H{o}s and P\'{o}sa proved that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs ${(\ell, z)}$ of integers where such a duality holds for the family of cycles of length $\ell$ modulo $z$. We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface., Comment: 37 pages, 2 figures

Let $\mathcal{F}$ be a family of graphs, and let $p,r$ be nonnegative integers. The \textsc{$(p,r,\mathcal{F})$-Covering} problem asks whether for a graph $G$ and an integer $k$, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^p\setminus N_G^r[D]$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$, where $G^p$ is the $p$-th power of $G$. The \textsc{$(p,r,\mathcal{F})$-Packing} problem asks whether for a graph $G$ and an integer $k$, $G^p$ has $k$ induced subgraphs $H_1,\ldots,H_k$ such that each $H_i$ is isomorphic to a graph in $\mathcal{F}$, and for distinct $i,j\in \{1, \ldots, k\}$, the distance between $V(H_i)$ and $V(H_j)$ in $G$ is larger than $r$. We show that for every fixed nonnegative integers $p,r$ and every fixed nonempty finite family $\mathcal{F}$ of connected graphs, the \textsc{$(p,r,\mathcal{F})$-Covering} problem with $p\leq2r+1$ and the \textsc{$(p,r,\mathcal{F})$-Packing} problem with $p\leq2\lfloor r/2\rfloor+1$ admit almost linear kernels on every nowhere dense class of graphs, and admit linear kernels on every class of graphs with bounded expansion, parameterized by the solution size $k$. We obtain the same kernels for their annotated variants. As corollaries, we prove that \textsc{Distance-$r$ Vertex Cover}, \textsc{Distance-$r$ Matching}, \textsc{$\mathcal{F}$-Free Vertex Deletion}, and \textsc{Induced-$\mathcal{F}$-Packing} for any fixed finite family $\mathcal{F}$ of connected graphs admit almost linear kernels on every nowhere dense class of graphs and linear kernels on every class of graphs with bounded expansion. Our results extend the results for \textsc{Distance-$r$ Dominating Set} by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017), and the result for \textsc{Distance-$r$ Independent Set} by Pilipczuk and Siebertz (EJC 2021)., Comment: 38 pages

We explore the quantization of a $(1+1)$-dimensional inhomogeneous scalar field theory in which Poincar\'{e} symmetry is explicitly broken. We show the `classical equivalence' between a scalar field theory on curved spacetime background and its corresponding inhomogeneous scalar field theory. This implies that a hidden connection may exist among some inhomogeneous field theories, which corresponds to general covariance in field theory on curved spacetime. Based on the classical equivalence, we propose how to quantize a specific field theory with broken Poincar\'{e} symmetry inspired by standard field theoretic approaches, canonical and algebraic methods, on curved spacetime. Consequently, we show that the Unruh effect can be realized in inhomogeneous field theory and propose that it may be tested by a condensed matter experiment. We suggest that an algebraic approach is appropriate for the quantization of a generic inhomogeneous field theory., Comment: 30 pages, 2 figures, plain LaTeX; v2, references added, minor changes; v3, minor changes, accepted version to EPJP

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomass\'e and Watrigant [J. ACM 2022] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced $f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced bandwidth, which implies and is stronger than bounded twin-width (reduced maximum degree). We show that every proper minor-closed class has bounded reduced bandwidth, which is qualitatively stronger than an analogous result of Bonnet et al.\ for bounded twin-width. In many instances, we also make quantitative improvements. For example, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$. We show that planar graphs have reduced bandwidth at most $466$ and twin-width at most $583$. Our bounds for graphs of Euler genus $\gamma$ are $O(\gamma)$. Lastly, we show that fixed powers of graphs in a proper minor-closed class have bounded reduced bandwidth (irrespective of the degree of the vertices). In particular, we show that map graphs of Euler genus $\gamma$ have reduced bandwidth $O(\gamma^4)$. Lastly, we separate twin-width and reduced bandwidth by showing that any infinite class of expanders excluding a fixed complete bipartite subgraph has unbounded reduced bandwidth, while there are bounded-degree expanders with twin-width at most 6., Comment: 35 pages, 4 figures

We study supersymmetric inhomogeneous field theories in 1+1 dimensions which have explicit coordinate dependence. Although translation symmetry is broken, part of supersymmetries can be maintained. In this paper, we consider the simplest inhomogeneous theories with one real scalar field, which possess an unbroken supersymmetry. The energy is bounded from below by the topological charge which is not necessarily nonnegative definite. The bound is saturated if the first-order Bogomolny equation is satisfied. Non-constant static supersymmetric solutions above the vacuum involve in general a zero mode although the system lacks translation invariance. We consider two inhomogeneous theories obtained by deforming supersymmetric sine-Gordon theory and $\phi^6$ theory. They are deformed either by overall inhomogeneous rescaling of the superpotential or by inhomogeneous deformation of the vacuum expectation value. We construct explicitly the most general supersymmetric solutions and obtain the BPS energy spectrum for arbitrary position-dependent deformations. Nature of the solutions and their energies depend only on the boundary values of the inhomogeneous functions. The vacuum of minimum energy is not necessarily a constant configuration. In some cases, we find a one-parameter family of degenerate solutions which include a non-vacuum constant solution as a special case., Comment: 29 pages, 5 figures, minor corrections, version published in JHEP

Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify F-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of F-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can compute every possible F-branchwidth, providing a unifying framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions., Comment: 42 pages, 6 figures

Every minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. However, for each fixed finite field $\mathbb F$, the list needs to contain only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these $\mathbb F$-representable excluded minors in general. We consider the class of matroids of path-width at most $k$ for fixed $k$. We prove that for a finite field $\mathbb F$, every $\mathbb F$-representable excluded minor for the class of matroids of path-width at most $k$ has at most $2^{|\mathbb{F}|^{O(k^2)}}$ elements. We can therefore compute, for any integer $k$ and a fixed finite field $\mathbb F$, the set of $\mathbb F$-representable excluded minors for the class of matroids of path-width $k$, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an $\mathbb F$-represented matroid is at most $k$. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs., Comment: 19 pages; slightly revised

We prove that there exists a function $f(k)=\mathcal{O}(k^2 \log k)$ such that for every $C_4$-free graph $G$ and every $k \in \mathbb{N}$, $G$ either contains $k$ vertex-disjoint holes of length at least $6$, or a set $X$ of at most $f(k)$ vertices such that $G-X$ has no hole of length at least $6$. This answers a question of Kim and Kwon [Erd\H{o}s-P\'osa property of chordless cycles and its applications. JCTB 2020]., Comment: 19 pages, 5 figures

An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_v\cap T_v\neq \emptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs, not many algorithmic applications on intersection digraphs have been developed. Motivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width, we introduce its directed analogue called `bi-mim-width' and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular, we show that as a natural extension of $H$-graphs, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020]. For applications, we introduce a novel framework of directed versions of locally checkable problems, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width, when a branch decomposition is given. Locally checkable problems include Kernel, Dominating Set, and Directed $H$-Homomorphism.

Erd\H{o}s and P\'{o}sa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $\ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties., Comment: 28 pages, 4 figures

We prove that for all positive integers $n$ and $k$, there exists an integer $N = N(n,k)$ satisfying the following. If $U$ is a set of $k$ direction vectors in the plane and $\mathcal{J}_U$ is the set of all line segments in direction $u$ for some $u\in U$, then for every $N$ families $\mathcal{F}_1, \ldots, \mathcal{F}_N$, each consisting of $n$ mutually disjoint segments in $\mathcal{J}_U$, there is a set $\{A_1, \ldots, A_n\}$ of $n$ disjoint segments in $\bigcup_{1\leq i\leq N}\mathcal{F}_i$ and distinct integers $p_1, \ldots, p_n\in \{1, \ldots, N\}$ satisfying that $A_j\in \mathcal{F}_{p_j}$ for all $j\in \{1, \ldots, n\}$. We generalize this property for underlying lines on fixed $k$ directions to $k$ families of simple curves with certain conditions.

Ultrashort photoemitted electron bunches can provide high electron currents within sub-picosecond timeframes, enabling time-resolved investigations of ultrafast physical processes with nanoscale resolution. Non-resonant conductive nanotips are typically employed to realize nanoscale photoelectron sources with high brightness. However, such emitters require complex non-scalable fabrication procedures featuring poor reproducibility. Planar resonant antennas fabricated via photolithography have been recently investigated, also because of their superior field enhancement properties. Nevertheless, the electron emission from these structures is parallel to the substrate plane, which limits their practical use as electron sources. In this work, we present an innovative out-of-plane, resonant nanoantenna design for field-driven photoemission enabled by high-resolution 3D printing. Numerical and experimental evidences demonstrate that gold-coated, terahertz resonant nanocones provide large local electric fields at their apex, automatically ensuring out-of-plane coherent electron emission and acceleration. We show that the resonant structures can be conveniently arranged in an array form, for a further significant electron extraction enhancement via a collective terahertz response. Remarkably, such collective behaviour can also be harvested to boost photoemission from an individual nano-source. Our approach opens the path for a new generation of photocathodes that can be reproducibly fabricated and designed at will, significantly relaxing the requirement for intense terahertz drivers., Comment: 19 pages, 4 figures, 1 table

The canonical tree-decomposition theorem, given by Robertson and Seymour in their seminal graph minors series, turns out to be one of the most important tool in structural and algorithmic graph theory. In this paper, we provide the canonical tree decomposition theorem for digraphs. More precisely, we construct directed tree-decompositions of digraphs that distinguish all their tangles of order $k$, for any fixed integer $k$, in polynomial time. As an application of this canonical tree-decomposition theorem, we provide the following result for the directed disjoint paths problem: For every fixed $k$ there is a polynomial-time algorithm which, on input $G$, and source and terminal vertices $(s_1, t_1), \dots, (s_k, t_k)$, either 1. determines that there is no set of pairwise vertex-disjoint paths connecting each source $s_i$ to its terminal $t_i$, or 2.finds a half-integral solution, i.e., outputs paths $P_1, \dots, P_k$ such that $P_i$ links $s_i$ to $t_i$, so that every vertex of the graph is contained in at most two paths. Given known hardness results for the directed disjoint paths problem, our result cannot be improved for general digraphs, neither to fixed-parameter tractability nor to fully vertex-disjoint directed paths. As far as we are aware, this is the first time to obtain a tractable result for the $k$-disjoint paths problem for general digraphs. We expect more applications of our canonical tree-decomposition for directed results.

We construct the 4-dimensional ${\cal N}=\frac12$ and ${\cal N}=1$ inhomogeneously mass-deformed super Yang-Mills theories from the ${\cal N} =1^*$ and ${\cal N} =2^*$ theories, respectively, and analyse their supersymmetric vacua. The inhomogeneity is attributed to the dependence of background fluxes in the type IIB supergravity on a single spatial coordinate. This gives rise to inhomogeneous mass functions in the ${\cal N} =4$ super Yang-Mills theory which describes the dynamics of D3-branes. The Killing spinor equations for those inhomogeneous theories lead to the supersymmetric vacuum equation and a boundary condition. We investigate two types of solutions in the $ {\cal N}=\frac12$ theory, corresponding to the cases of asymptotically constant mass functions and periodic mass functions. For the former case, the boundary condition gives a relation between the parameters of two possibly distinct vacua at the asymptotic boundaries. Brane interpretations for corresponding vacuum solutions in type IIB supergravity are also discussed. For the latter case, we obtain explicit forms of the periodic vacuum solutions., Comment: 22 pages

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role from tree-width and path-width. As such, it is natural to examine if for every tree~$T$, the class of graphs that do not contain $T$ as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever $T$ is a tree that is not a caterpillar. We conjecture that the statement is true if $T$ is a caterpillar. We are also able to give partial confirmation of this conjecture by proving: (1) for every tree $T$, the class of $T$-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if $T$ is a caterpillar; (2) for every caterpillar $T$ on at most four vertices, the class of $T$-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider $T=P_4$ and $T=K_{1,3}$, but we follow a general strategy: first we show that the class of $T$-pivot-minor-free graphs is contained in some class of $(H_1,H_2)$-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of $(K_3,S_{1,2,2})$-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width., Comment: 26 pages, 5 figures; accepted to SIAM Journal on Discrete Mathematics

The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time $2^{O(tw)}n^{O(1)}$, for Feedback Vertex Set and connected versions of the classical graph problems (such as Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and Multiway Cut are unlikely to have such running times. More precisely, we match algorithms running in time $2^{O(tw \log tw)}n^{O(1)}$ with tight lower bounds under the Exponential-Time Hypothesis (ETH), ruling out $2^{o(tw \log tw)}n^{O(1)}$, where $n$ is the number of vertices and $tw$ is the treewidth of the input graph. Our algorithms extend to the weighted case, while our lower bounds also hold for the larger parameter pathwidth and do not require weights. We also show that, in contrast to Odd Cycle Transversal, there is no $2^{o(tw \log tw)}n^{O(1)}$-time algorithm for Even Cycle Transversal under the ETH., Comment: 25 pages, 5 figures

We prove that there exists a function $f:\mathbb{N}\rightarrow \mathbb{R}$ such that every directed graph $G$ contains either $k$ directed odd cycles where every vertex of $G$ is contained in at most two of them, or a set of at most $f(k)$ vertices meeting all directed odd cycles. We also give a polynomial-time algorithm for fixed $k$ which outputs one of the two outcomes. Using this algorithmic result, we give a polynomial-time algorithm for fixed $k$ to decide whether such $k$ directed odd cycles exist, or there are no $k$ vertex-disjoint directed odd cycles. This extends the half-integral Erd\H{o}s-P\'osa theorem for undirected odd cycles by Reed [Combinatorica 1999] to directed graphs., Comment: 21 pages, 6 figures

We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First, the cliques in the partition can be arranged in a tree structure, and second, each clique is of arbitrary size. We provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs, and give a polynomial-time algorithm that given any graph, either finds an obstruction, or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices is in FPT parameterized by k on well-partitioned chordal graphs, while on chordal graphs, these problems are only known to be in XP. From the other end, we observe that there are problems that are polynomial-time solvable on split graphs, but become NP-complete on well-partitioned chordal graphs.

We construct renormalized holographic entanglement entropy (HEE) and subregion complexity (HSC) in the CV conjecture for asymptotically AdS$_4$ and AdS$_5$ geometries under relevant perturbations. Using the holographic renormalization method developed in the gauge/gravity duality, we obtain counter terms which are invariant under coordinate choices. We explicitly define different forms of renormalized HEE and HSC, according to conformal dimensions of relevant operators in the $d=3$ and $d=4$ dual field theories. We use a general embedding for arbitrary entangling subregions and showed that any choice of the coordinate system gives the same form of the counter terms, since they are written in terms of curvature invariants and scalar fields on the boundaries. We show an explicit example of our general procedure. Intriguingly, we find that a divergent term of the HSC in the asymptotically AdS$_5$ geometry under relevant perturbations with operators of conformal dimensions in the range $0< \Delta < \frac{1}{2}\,\, {\rm and} \,\, \frac{7}{2}< \Delta < 4$ cannot be cancelled out by adding any coordinate invariant counter term. This implies that the HSCs in these ranges of the conformal dimensions are not renormalizable covariantly., Comment: 31 pages, 1 figure, references added

Given a family $\mathcal{I}$ of independent sets in a graph, a rainbow independent set is an independent set $I$ such that there is an injection $\phi\colon I\to \mathcal{I}$ where for each $v\in I$, $v$ is contained in $\phi(v)$. Aharoni, Briggs, J. Kim, and M. Kim [Rainbow independent sets in certain classes of graphs. arXiv:1909.13143] determined for various graph classes $\mathcal{C}$ whether $\mathcal{C}$ satisfies a property that for every $n$, there exists $N=N(\mathcal{C},n)$ such that every family of $N$ independent sets of size $n$ in a graph in $\mathcal{C}$ contains a rainbow independent set of size $n$. In this paper, we add two dense graph classes satisfying this property, namely, the class of graphs of bounded neighborhood diversity and the class of $r$-powers of graphs in a bounded expansion class.

In this paper we study the thermodynamics of black branes with a modulated complex scalar in the context of bulk and boundary theories. The modulation induces inhomogeneity to the dual field theory, anisotropic pressure, and brane charge to the bulk geometry. The first law of thermodynamics and the Smarr relation are obtained using the off-shell ADT and the reduced action formalisms. We discuss the prescription for the mass of black branes, which relies on relevant and marginal deformations in the dual field theory. One of the cases is the gravity dual to a ABJM model with a sinusoidal mass function depending on a spatial coordinate. This is the first study of the deformed ABJM model at finite temperature including bulk thermodynamics., Comment: 28 pages, 1 figure

We study dual geometries to a deformed ABJM model with spatially dependent source functions at finite temperature. These source functions are proportional to the mass function $m(x)= m_0 \sin k x$ and its derivative $m'(x)$. As dual geometries, we find hairy black branes and AdS solitons corresponding to deconfinement phase and confining phase of the dual field theory, respectively. It turns out that the hairy AdS solitons have lower free energy than the black branes when the Hawking temperature is smaller than the confining scale. Therefore the dual system undergoes the first order phase transition. Even though our study is limited to the so-called Q-lattice ansatz, the solution space contains a set of solutions dual to a supersymmetric mass deformation. As a physical quantity to probe the confining phase, we investigate the holographic entanglement entropy and discuss its behavior in terms of modulation effect., Comment: 22 pages, 8 figures, Typos corrected, a figure added, appendix added, clarifications added, accepted version in JHEP

For a non-negative integer $\ell$, the $\ell$-leaf power of a tree $T$ is a simple graph $G$ on the leaves of $T$ such that two vertices are adjacent in $G$ if and only if their distance in $T$ is at most $\ell$. We provide a polynomial kernel for the problem of deciding whether we can delete at most $k$ vertices to make an input graph a $3$-leaf power of some tree. More specifically, we present a polynomial-time algorithm for an input instance $(G,k)$ for the problem to output an equivalent instance $(G',k')$ such that $k'\leq k$ and $G'$ has at most $O(k^{14})$ vertices., Comment: 28 pages, 1 figure

Shrub-depth and rank-depth are dense analogues of the tree-depth of a graph. It is well known that a graph has large tree-depth if and only if it has a long path as a subgraph. We prove an analogous statement for shrub-depth and rank-depth, which was conjectured by Hlin\v{e}n\'y, Kwon, Obdr\v{z}\'alek, and Ordyniak [Tree-depth and vertex-minors, European J.~Combin. 2016]. Namely, we prove that a graph has large rank-depth if and only if it has a vertex-minor isomorphic to a long path. This implies that for every integer $t$, the class of graphs with no vertex-minor isomorphic to the path on $t$ vertices has bounded shrub-depth., Comment: 19 pages, 5 figures; accepted to Journal of Combinatorial Theory Ser. B

Recently, ${\cal N} =3$ mass-deformed ABJM model with arbitrary mass-function depending on a spatial coordinate was constructed. In addition to the ${\cal N} = 3$ case, we construct lower supersymmetric ${\cal N} =1$ and ${\cal N} =2$ inhomogeneously mass-deformed ABJM (ImABJM) models, which require three and two arbitrary mass-functions, respectively. We also construct general vacuum solutions of the ${\cal N} = 3$ ImABJM model for any periodic mass-function. There are two classes of vacua, which are diagonal type and GRVV type according to reference value of mass-functions. We provide explicit examples of the vacuum solutions and discuss related operators., Comment: 30 pages, 4 figures, Typos corrected