Search

The $d$-Cut problem is to decide if a graph has an edge cut such that each vertex has at most $d$ neighbours at the opposite side of the cut. If $d=1$, we obtain the intensively studied Matching Cut problem. The $d$-Cut problem has been studied as well, but a systematic study for special graph classes was lacking. We initiate such a study and consider classes of bounded diameter, bounded radius and $H$-free graphs. We prove that for all $d\geq 2$, $d$-Cut is polynomial-time solvable for graphs of diameter $2$, $(P_3+P_4)$-free graphs and $P_5$-free graphs. These results extend known results for $d=1$. However, we also prove several NP-hardness results for $d$-Cut that contrast known polynomial-time results for $d=1$. Our results lead to full dichotomies for bounded diameter and bounded radius and to almost-complete dichotomies for $H$-free graphs.

A recent paper describes a framework for studying the computational complexity of graph problems on monotone classes, that is those omitting a set of graphs as a subgraph. If the problems lie in the framework, and many do, then the computational complexity can be described for all monotone classes defined by a finite set of omitted subgraphs. It is known that certain homomorphism problems, e.g. $C_5$-Colouring, do not sit in the framework. By contrast, we show that the more general problem of Graph Homomorphism does sit in the framework. The original framework had examples where hard versus easy were NP-complete versus P, or at least quadratic versus almost linear. We give the first example of a problem in the framework such that hardness is in the polynomial hierarchy above NP. Considering a variant of the colouring game as studied by Bodlaender, we show that with the restriction of bounded alternation, the list version of this problem is contained in the framework. The hard cases are $\Pi_{2k}^\mathrm{P}$-complete and the easy cases are in P. The cases in P comprise those classes for which the pathwidth is bounded. Bodlaender explains that Sequential $3$-Colouring Construction Game is in P on classes with bounded vertex separation number, which coincides with bounded pathwidth on unordered graphs. However, these graphs are ordered with a playing order for the two players, which corresponds to a prefix pattern in a quantified formula. We prove that Sequential $3$-Colouring Construction Game is Pspace-complete on some class of bounded pathwidth, using a celebrated result of Atserias and Oliva. We consider several locally constrained variants of the homomorphism problem. Like $C_5$-Colouring, none of these is in the framework. However, when we consider the bounded-degree restrictions, we prove that each of these problems is in our framework.

We study Steiner Forest on $H$-subgraph-free graphs, that is, graphs that do not contain some fixed graph $H$ as a (not necessarily induced) subgraph. We are motivated by a recent framework that completely characterizes the complexity of many problems on $H$-subgraph-free graphs. However, in contrast to e.g. the related Steiner Tree problem, Steiner Forest falls outside this framework. Hence, the complexity of Steiner Forest on $H$-subgraph-free graphs remained tantalizingly open. In this paper, we make significant progress towards determining the complexity of Steiner Forest on $H$-subgraph-free graphs. Our main results are four novel polynomial-time algorithms for different excluded graphs $H$ that are central to further understand its complexity. Along the way, we study the complexity of Steiner Forest for graphs with a small $c$-deletion set, that is, a small set $S$ of vertices such that each component of $G-S$ has size at most $c$. Using this parameter, we give two noteworthy algorithms that we later employ as subroutines. First, we prove Steiner Forest is FPT parameterized by $|S|$ when $c=1$ (i.e. the vertex cover number). Second, we prove Steiner Forest is polynomial-time solvable for graphs with a 2-deletion set of size at most 2. The latter result is tight, as the problem is NP-complete for graphs with a 3-deletion set of size 2.

For any finite set $\mathcal{H} = \{H_1,\ldots,H_p\}$ of graphs, a graph is $\mathcal{H}$-subgraph-free if it does not contain any of $H_1,\ldots,H_p$ as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity is determined on classes of $\mathcal{H}$-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most~$3$ and examine their complexity on $H$-subgraph-free graph classes where $H$ is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree $3$. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.

For a fixed set ${\cal H}$ of graphs, a graph $G$ is ${\cal H}$-subgraph-free if $G$ does not contain any $H \in {\cal H}$ as a (not necessarily induced) subgraph. A recently proposed framework gives a complete classification on ${\cal H}$-subgraph-free graphs (for finite sets ${\cal H}$) for problems that are solvable in polynomial time on graph classes of bounded treewidth, NP-complete on subcubic graphs, and whose NP-hardness is preserved under edge subdivision. While a lot of problems satisfy these conditions, there are also many problems that do not satisfy all three conditions and for which the complexity in ${\cal H}$-subgraph-free graphs is unknown. We study problems for which only the first two conditions of the framework hold (they are solvable in polynomial time on classes of bounded treewidth and NP-complete on subcubic graphs, but NP-hardness is not preserved under edge subdivision). In particular, we make inroads into the classification of the complexity of four such problems: Hamilton Cycle, $k$-Induced Disjoint Paths, $C_5$-Colouring and Star $3$-Colouring. Although we do not complete the classifications, we show that the boundary between polynomial time and NP-complete differs among our problems and also from problems that do satisfy all three conditions of the framework, in particular when we forbid certain subdivisions of the ``H''-graph (the graph that looks like the letter ``H''). Hence, we exhibit a rich complexity landscape among problems for ${\cal H}$-subgraph-free graph classes.

For any particular class of graphs, algorithms for computational problems restricted to the class often rely on structural properties that depend on the specific problem at hand. This begs the question if a large set of such results can be explained by some common problem conditions. We propose such conditions for $HH$-subgraph-free graphs. For a set of graphs $HH$, a graph $G$ is $HH$-subgraph-free if $G$ does not contain any of graph from $H$ as a subgraph. Our conditions are easy to state. A graph problem must be efficiently solvable on graphs of bounded treewidth, computationally hard on subcubic graphs, and computational hardness must be preserved under edge subdivision of subcubic graphs. Our meta-classification says that if a graph problem satisfies all three conditions, then for every finite set $HH$, it is ``efficiently solvable'' on $HH$-subgraph-free graphs if $HH$ contains a disjoint union of one or more paths and subdivided claws, and is ``computationally hard'' otherwise. We illustrate the broad applicability of our meta-classification by obtaining a dichotomy between polynomial-time solvability and NP-completeness for many well-known partitioning, covering and packing problems, network design problems and width parameter problems. For other problems, we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). The proposed framework thus gives a simple pathway to determine the complexity of graph problems on $HH$-subgraph-free graphs. This is confirmed even more by the fact that along the way, we uncover and resolve several open questions from the literature.

We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree $3$ (also known as subcubic graphs). This improves on a previous degree bound of $11$. Our NP-completeness result holds even for subcubic graphs that are planar., Comment: Appeared in Proceedings of SWAT 2024

Strategies based on the active targeting of tumor cells are emerging as smart and efficient nanomedical procedures. Folic acid (FA) is a vitamin and a well-established tumor targeting agent because of its strong affinity for the folate receptor (FR), which is an overexpressed protein on the cell membranes of the tumor cells. FA can be successfully anchored to several nanocarriers, including inorganic nanoparticles (NPs) based on transition metal oxides. Among them, TiO$_{2}$ is extremely interesting because of its excellent photoabsorption and photocatalytic properties, which can be exploited in photodynamic therapy. However, it is not yet clear in which respects direct anchoring of FA to the NP or the use of spacers, based on polyethylene glycol (PEG) chains, are different and whether one approach is better than the other. In this work, we combine Quantum Mechanics (QM) and Classical Molecular Dynamics (MD) to design and optimize the FA functionalization on bare and PEGylated TiO$_{2}$ models and to study the dynamical behavior of the resulting nanoconjugates in pure water environment and in physiological conditions. We observe that they are chemically stable, even under the effect of increasing temperature (up to 500 K). Using the results from long MD simulations (100 ns) and from free energy calculations, we determine how the density of FA molecules on the TiO$_{2}$ NP and the presence of PEG spacers impact on the actual exposure of the ligands, especially by affecting the extent of FA-FA intermolecular interactions, which are detrimental for the targeting ability of FA towards the folate receptor. This analysis provides a solid and rational basis for experimentalists to define the optimal FA density and the more appropriate mode of anchoring to the carrier, according to the final purpose of the nanoconjugate.

The conjugation of high-affinity cRGD-containing peptides is a promising approach in nanomedicine to efficiently reduce off-targeting effects and enhance the cellular uptake by integrin-overexpressing tumor cells. Herein we utilize atomistic molecular dynamics simulations to evaluate key structural-functional parameters of these targeting ligands for an effective binding activity towards $\alpha_V\beta_3$ integrins. An increasing number of cRGD ligands is conjugated to PEG chains grafted to highly curved TiO$_2$ nanoparticles to unveil the impact of cRGD density on the ligand's presentation, stability, and conformation in an explicit aqueous environment. We find that a low density leads to an optimal spatial presentation of cRGD ligands out of the "stealth" PEGylated layer around the nanosystem, favoring a straight upward orientation and spaced distribution of the targeting ligands in the bulk-water phase. On the contrary, high densities favor clustering and internalization of cRGD ligands in the inner region of the PEGylated layer, driven by a concerted mechanism of enhanced ligand-ligand interactions and reduced water accessibility over the ligand's molecular surface. These findings strongly suggest that the ligand density modulation is a key factor in the design of cRGD-targeting nanodevices to maximize their binding efficiency into over-expressed $\alpha_V\beta_3$ integrin receptors.

Paths $P^1,\ldots,P^k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P^i$ and $P^j$ have neither common vertices nor adjacent vertices. For a fixed integer $k$, the $k$-Induced Disjoint Paths problem is to decide if a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P^i$ such that each $P^i$ starts from $s_i$ and ends at $t_i$. Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer $k$, a classical result from the literature states that even $2$-Induced Disjoint Paths is NP-complete. We prove new complexity results for $k$-Induced Disjoint Paths if the input is restricted to $H$-free graphs, that is, graphs without a fixed graph $H$ as an induced subgraph. We compare our results with a complexity dichotomy for Induced Disjoint Paths, the variant where $k$ is part of the input.

Paths $P_1,\ldots, P_k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P_i$ and $P_j$ have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P_i$ such that each $P_i$ starts from $s_i$ and ends at $t_i$. This is a classical graph problem that is NP-complete even for $k=2$. We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

For a fixed integer, the $k$-Colouring problem is to decide if the vertices of a graph can be coloured with at most $k$ colours for an integer $k$, such that no two adjacent vertices are coloured alike. A graph $G$ is $H$-free if $G$ does not contain $H$ as an induced subgraph. It is known that for all $k\geq 3$, the $k$-Colouring problem is NP-complete for $H$-free graphs if $H$ contains an induced claw or cycle. The case where $H$ contains a cycle follows from the known result that the problem is NP-complete even for graphs of arbitrarily large fixed girth. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

Doxorubicin (DOX) is one of the most efficient antitumor drugs employed in numerous cancer therapies. Its incorporation into lipid-based nanocarriers, such as liposomes, improves the drug targeting into tumor cells and reduces drug side effects. The carriers' lipid composition is expected to affect the interactions of DOX and its partitioning into liposomal membranes. To get a rational insight into this aspect and determine promising lipid compositions, we use numerical simulations, which provide unique information on DOX-membrane interactions at the atomic level of resolution. In particular, we combine classical molecular dynamics simulations and free energy calculations to elucidate the mechanism of penetration of a protonated Doxorubicin molecule (DOX+) into potential liposome membranes, here modeled as lipid bilayers based on mixtures of phosphatidylcholine (PC), sphingomyelin (SM) and cholesterol lipid molecules, of different compositions and lipid phases. Moreover, we analyze DOX+ partitioning into relevant regions of SM-based lipid bilayer systems using a combination of free energy methods. Our results show that DOX+ penetration and partitioning are facilitated into less tightly packed SM-based membranes and are dependent on lipid composition. This work paves the way to further investigations of optimal formulations for lipid-based carriers, such as those associated with pH-responsive membranes.

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for $H$-free graphs. If $k$ is fixed, we obtain the $k$-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every $k \geq 1$. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of $k$-Disjoint Connected Subgraphs for $H$-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for $H$-free graphs as for Disjoint Paths.

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of $H$-free graphs, that is, graphs that do not contain some graph $H$ as an induced subgraph, have proven to be an ideal testbed for such a complexity study. However, if the forbidden graph $H$ contains a cycle or claw, then these problems often stay NP-complete. A recent complexity study on the $k$-Colouring problem shows that we may still obtain tractable results if we also bound the diameter of the $H$-free input graph. We continue this line of research by initiating a complexity study on the impact of bounding the diameter for a variety of classical vertex partitioning problems restricted to $H$-free graphs. We prove that bounding the diameter does not help for Independent Set, but leads to new tractable cases for problems closely related to 3-Colouring. That is, we show that Near-Bipartiteness, Independent Feedback Vertex Set, Independent Odd Cycle Transversal, Acyclic 3-Colouring and Star 3-Colouring are all polynomial-time solvable for chair-free graphs of bounded diameter. To obtain these results we exploit a new structural property of 3-colourable chair-free graphs.

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H_1,...,H_n so that there exists an edge from every vertex of H_i to every vertex of H_j if and only if i

We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as $L(1,1)$-Labelling and we also consider the framework of $L(a,b)$-Labelling. We prove a number of (almost-)complete complexity classifications. In particular, we show that for graphs of diameter at most $d$, Acyclic $3$-Colouring is polynomial-time solvable if $d\leq 2$ but NP-complete if $d\geq 4$, and Star $3$-Colouring is polynomial-time solvable if $d\leq 3$ but NP-complete for $d\geq 8$. As far as we are aware, Star $3$-Colouring is the first problem that exhibits a complexity jump for some $d\geq 3$. Our third main result is that $L(1,2)$-Labelling is NP-complete for graphs of diameter $2$; we relate the latter problem to a special case of Hamiltonian Path.

In this paper we focus on artificial intelligence (AI) for governance, not governance for AI, and on just one aspect of governance, namely ethics audit. Different kinds of ethical audit bots are possible, but who makes the choices and what are the implications? In this paper, we do not provide ethical/philosophical solutions, but rather focus on the technical aspects of what an AI-based solution for validating the ethical soundness of a target system would be like. We propose a system that is able to conduct an ethical audit of a target system, given certain socio-technical conditions. To be more specific, we propose the creation of a bot that is able to support organisations in ensuring that their software development lifecycles contain processes that meet certain ethical standards., Comment: 5 pages, short paper, 15th Multi Conference on Computer Science and Information Systems, 20-23 July 2021

Ethics is sometimes considered to be too abstract to be meaningfully implemented in artificial intelligence (AI). In this paper, we reflect on other aspects of computing that were previously considered to be very abstract. Yet, these are now accepted as being done very well by computers. These tasks have ranged from multiple aspects of software engineering to mathematics to conversation in natural language with humans. This was done by automating the simplest possible step and then building on it to perform more complex tasks. We wonder if ethical AI might be similarly achieved and advocate the process of automation as key step in making AI take ethical decisions. The key contribution of this paper is to reflect on how automation was introduced into domains previously considered too abstract for computers., Comment: 4 pages, 15th Multi Conference on Computer Science and Information Systems, 20-23 July 2021

For $k\geq 1$, a $k$-colouring $c$ of $G$ is a mapping from $V(G)$ to $\{1,2,\ldots,k\}$ such that $c(u)\neq c(v)$ for any two non-adjacent vertices $u$ and $v$. The $k$-Colouring problem is to decide if a graph $G$ has a $k$-colouring. For a family of graphs ${\cal H}$, a graph $G$ is ${\cal H}$-free if $G$ does not contain any graph from ${\cal H}$ as an induced subgraph. Let $C_s$ be the $s$-vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of $3$-Colouring for $(C_3,\ldots,C_s)$-free graphs and $H$-free graphs where $H$ is some polyad. Here, we prove for certain small values of $s$ that $3$-Colouring is polynomial-time solvable for $C_s$-free graphs of diameter $2$ and $(C_4,C_s)$-free graphs of diameter $2$. In fact, our results hold for the more general problem List $3$-Colouring. We complement these results with some hardness result for diameter $4$.

The accurate description of iron oxides/water interfaces requires reliable force field parameters that can be developed through the comparison with sophisticated quantum mechanical calculations. Here a set of CLASS2 force field parameters is optimized to describe the Fe-Owater cross interaction through comparison with hybrid density functional theory (HSE06) calculations of the potential energy function for a single water molecule adsorbed on the Fe3O4 (001) surface and with density functional tight binding (DFTB+U) molecular dynamics simulations for a water tri-layer on the same surface. The performance of the new parameters is assessed through the analysis of the number density profile of a water bulk (12 nm) sandwiched between two magnetite slabs of large surface area. Their transferability is tested for the water adsorption on the curved surface of a spherical Fe3O4 nanoparticle of realistic size (2.5 nm).

A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable for every hereditary graph class that is not equal to the class of all graphs.

We consider the L(p,q)-Edge-Labelling problem, which is the edge variant of the well-known L(p,q)-Labelling problem. So far, the complexity of this problem was only partially classified. We complete this study for all nonnegative p and q, by showing that, whenever (p,q) is not (0,0), L(p,q)-Edge-Labelling problem is NP-complete. We do this by proving that for all nonnegative p and q, except p=q=0, there exists an integer k so that L(p,q)-Edge-k-Labelling is NP-complete.

A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as $L(1,1)$-Labelling). A classical complexity result on Colouring is a well-known dichotomy for $H$-free graphs (a graph is $H$-free if it does not contain $H$ as an induced subgraph). In contrast, there is no systematic study into the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring despite numerous algorithmic and structural results that have appeared over the years. We perform such a study and give almost complete complexity classifications for Acyclic Colouring, Star Colouring and Injective Colouring on $H$-free graphs (for each of the problems, we have one open case). Moreover, we give full complexity classifications if the number of colours $k$ is fixed, that is, not part of the input. From our study it follows that for fixed $k$ the three problems behave in the same way, but this is no longer true if $k$ is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs of multigraphs., Comment: Extended abstracts appeared / will appear at ESA 2020 and CSR 2021

In this work we investigate the Fe$_3$O$_4$(001) surface/water interface by combining several theoretical approaches, ranging from a hybrid functional method (HSE06) to density-functional tight-binding (DFTB) to molecular mechanics (MM). First, we assess the accuracy of the DFTB method to reproduce correctly HSE06 results on structural details and energetics and available experimental data for the adsorption of isolated water, dimers, trimers, etc. up to a water monolayer. Secondly, we build two possible configurations of a second and a third overlayer and perform molecular dynamics simulations with DFTB, monitoring the water orientation, the H-bond network, and ordered water structures formation. To make our models more realistic, we then build a 12-nm thick water multilayer on top of the Fe$_3$O$_4$(001) surface slab model, which we investigate through MM molecular dynamics. The water layers structuring, revealed by the analysis of the atomic positions from a long MM-MD run for this large MM model, extends up to about 6-7 {\AA} and nicely compares with that observed for a water trilayer model. However, MM and DFTB MD simulations show some discrepancy due to the poor description of the Fe--OH2 distance in MM that calls for further work in the parametrization of the model.

We develop a method to identify the BPS states in the Hilbert space of a supersymmetric field theory on a generic curved space which preserves at least two real supercharges. We also propose a one-to-one map between BPS states in d-dimensional field theories and states that contribute to the supersymmetric partition function of a corresponding (d-1)-dimensional field theory. As an application we obtain the superconformal index on rounded and squashed three spheres, and we show a natural reduction of the respective indices to the three-dimensional exact partition functions. We discuss the validity of the correspondence both at the perturbative and at the non-perturbative level and exploit the idea to uplift the computation of the exact supersymmetric partition function on a general manifold to a higher dimensional index., Comment: 25 pages, 1 figure, typos fixed

We discuss and provide nontrivial evidence for a large class of dualities in three-dimensional field theories with different gauge groups. We match the full partition functions of the dual phases for any value of the couplings to underpin our proposals. We focus on two classes of models. The first class, motivated by the AdS/CFT conjecture, consists of necklace U(N) quiver gauge theories with non chiral matter fields. We also consider orientifold projections and establish dualities among necklace quivers with alternating orthogonal and symplectic groups. The second class consists of theories with tensor matter fields with free theory duals. In most of these cases the R-symmetry mixes with IR accidental symmetries and we develop the prescription to include their contribution into the partition function and the extremization problem accordingly., Comment: 38 pages, 3 figure, using jheppub

We compute the large N limit of the localized three dimensional free energy of various field theories with known proposed AdS duals. We show that vector-like theories agree with the expected supergravity results, and with the conjectured F-theorem. We also check that the large N free energy is preserved by the three dimensional Seiberg duality for general classes of vector like theories. Then we analyze the behavior of the free energy of chiral-like theories by applying a new proposal. The proposal is based on the restoration of a discrete symmetry on the free energy before the extremization. We apply this procedure at strong coupling in some examples and we discuss the results. We conclude the paper by proposing an alternative geometrical expression for the free energy., Comment: 40 pages, 7 figures, using jheppub.sty, references added

We study the localized free energy on S^3 of three-dimensional N=2 Chern-Simons matter theories at weak coupling. We compute the two loop R charge in three different ways, namely by the standard perturbative approach, by extremizing the localized partition function at finite N and by applying the standard saddle point approximation for large N. We show that the latter approach does not reproduce the expected result when chiral theories are considered. We circumvent these problems by restoring a reflection symmetry on the eigenvalues in the free energy. Thanks to this symmetrization we find that the three methods employed agree. In particular we match the computation for a model whose four dimensional parent is the quiver gauge theory describing D3 branes probing the Hirzebruch surface. We conclude by commenting on the application of our results and to the strong coupling regime., Comment: 20 pages, 1 figure, using jheppub.sty

We discuss exotic properties of charged hydrodynamical systems, in the broken superconducting phase, probed by electromagnetic waves. Motivated by general arguments from hydrodynamics, we observe that negative refraction, namely the propagation in opposite directions of the phase velocities and of the energy flux, is expected for low enough frequencies. We corroborate this general idea by analyzing a holographic superconductor in the AdS/CFT correspondence, where the response functions can be explicitly computed. We study the dual gravitational theory both in the probe and in the backreacted case. We find that, while in the first case the refractive index is positive at every frequency, in the second case there is negative refraction at low enough frequencies. This is in agreement with hydrodynamic considerations., Comment: 26 pages, 28 figures

We propose an extension of the F-maximization principle to take into account the effects of non-superconformality. Guided by a four-dimensional analog, we formulate a modification of the free energy via the Lagrange multiplier technique. We conjecture that the Lagrange multiplier plays the same role as the coupling constant, at least at weak coupling. We check our proposal in many examples with unitary, symplectic and orthogonal gauge groups., Comment: 19 pages, using jheppub.sty, references added, final version published on JHEP

The three dimensional exact R symmetry of N=2 SCFTs extremizes the partition function localized on a three sphere. Here we verify this statement at weak coupling. We give a detailed analysis for two classes of models. The first one is an SU(N)_k gauge theory at large k with both fundamental and adjoint matter fields, while the second is a flavored version of the ABJ theory, where the CS levels are large but they do not necessarily sum up to zero. We study in both cases superpotential deformations and compute the R charges at different fixed points. When these fixed points are connected by an RG flow we explicitly verify that the free energy decreases at the endpoints of the flow between the fixed points, corroborating the conjecture of an F-theorem in three dimensions., Comment: 28 pages, 3 figures, JHEP.cls, minor corrections, references added

We study a model describing a four-dimensional holographic superconductor whose properties depend non-trivially on a particular spatial direction, namely a Josephson junction. We analyze the parameter dependence of the condensate and compare it to the condensed matter expectations., Comment: 10 pages, 4 figures

We study a fully backreacted holographic model of a four-dimensional superconductor by including a higher curvature interaction in the bulk action. We study how the critical temperature and the field theory condensate vary in this model and conclude that positive higher curvature couplings make the condensation harder. We also compute the conductivity, finding significant deviations from the conjectured universal frequency gap to critical temperature ratio., Comment: 16 pages, 6 figures; v2: published version plus one reference added

We study dynamical supersymmetry breaking in vector-like superconformal N=1 gauge theories. We find appropriate deformations of the superpotential to overcome the problem of the instability of the non supersymmetric vacuum. The request for long lifetime translates into constraints on the physical couplings which in this regime can be controlled through efficient RG analysis., Comment: 17 pages, 7 figures, JHEP3.cls

According to the AdS4/CFT3 correspondence, N=2 supersymmetric Chern-Simons matter theories should have a stable fixed point in the infrared. In order to support this prediction we study RG flows of two-level Chern-Simons matter theories with/without flavors induced by the most general marginal superpotential compatible with N=2 supersymmetry. At two loops we determine the complete spectrum of fixed points and study their IR stability. Our analysis covers a large class of models including perturbations of the ABJM/ABJ theories with and without flavors, N=2,3 theories with different CS levels corresponding to turning on a Romans mass and beta-deformations. In all cases we find curves (or surfaces) of fixed points which are globally IR stable but locally unstable in the following sense: The system has only one direction of stability which in the ABJM case coincides with the maximal global symmetry preserving perturbation, whereas along any other direction it flows to a different fixed point on the surface. The question of conformal invariance vs. finiteness is also addressed: While in general vanishing beta-functions imply two-loop finiteness, we find a particular set of flavored theories where this is no longer true., Comment: 1+30 pages, 8 figures; v2: references added

We consider marginal deformations of the superconformal ABJM/ABJ models which preserve N=2 supersymmetry. We determine perturbatively the spectrum of fixed points and study their infrared stability. We find a closed line of fixed points which is IR stable. The fixed point corresponding to the ABJM/ABJ models is stable under marginal deformations which respect the original SU(2)xSU(2) invariance, while deformations which break this group destabilize the theory which then flows to a less symmetric fixed point. We discuss the addition of flavor degrees of freedom. We prove that in general a flavor marginal superpotential does not destabilize the system in the IR. An exception is represented by a marginal coupling which mixes matter charged under different gauge sectors. Finally, we consider the case of relevant deformations which should drive the system to a strongly coupled IR fixed point recently investigated in arXiv:0909.2036 [hep-th]., Comment: 1+11 pages, 4 figures; v2: minor corrections

We analyze metastable supersymmetry breaking in 3D WZ models. We study the regime of validity of the perturbative computation for superpotentials with marginal and relevant couplings. Lifetime of the metastable states in presence of a triangular potential barrier is estimated., Comment: 1+16 pages, 2 figures, JHEP3.cls

Renormalizable nonanticommutative SYM theories with chiral matter in the adjoint representation of the gauge group have been recently constructed in [arXiv:0901.3094]. In the present paper we focus on the U*(1) case with matter interacting through a cubic superpotential. For a single flavor, in a superspace setup and manifest background covariant approach we perform the complete one-loop renormalization and compute the beta-functions for all couplings appearing in the action. We then generalize the calculation to the case of SU(3) flavor matter with a cubic superpotential viewed as a nontrivial NAC generalization of the ordinary abelian N=4 SYM and its marginal deformations. We find that, as in the ordinary commutative case, the NAC N=4 theory is one-loop finite. We provide general arguments in support of all-loop finiteness. Instead, deforming the superpotential by marginal operators gives rise to beta-functions which are in general non-vanishing. We study the spectrum of fixed points and the RG flows. We find that nonanticommutativity always makes the fixed points unstable., Comment: 1+30 pages, 5 figures

We consider nonanticommutative SYM theories with chiral matter in the adjoint representation of the SU(N) x U(1) gauge group. In a superspace setup and manifest background covariant approach we investigate the one-loop renormalization of the theory when a cubic superpotential is present. The structure of the divergent terms reveals that the theory simply obtained from the ordinary one by trading products for star products is not renormalizable. Moreover, because of the different renormalization undergone by the abelian field compared to the non-abelian ones, the superpotential seems to be incompatible with the requests of renormalizability, gauge and N=1/2 invariance. However, by a suitable modification of the quadratic action for the U(1) (anti)chiral superfields and the addition of extra couplings, we find an action which is one-loop renormalizable and manifestly N=1/2 supersymmetric and supergauge invariant. We conclude that interacting matter can be safely introduced in NAC gauge theories, in contrast with previous results., Comment: LaTex, 38 pages, 3 figures