Search

We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one vertex from the bipartite part of any other bag, while the width of such decomposition measures how far the bags are from being bipartite. Adapted from a tree decomposition originally defined by Demaine, Hajiaghayi, and Kawarabayashi [SODA 2010] and explicitly defined by Tazari [Th. Comp. Sci. 2012], bipartite treewidth appears to play a crucial role for solving problems related to odd-minors, which have recently attracted considerable attention. As a first step toward a theory for solving these problems efficiently, the main goal of this paper is to develop dynamic programming techniques to solve problems on graphs of small bipartite treewidth. For such graphs, we provide a number of para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that $K_t$-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are $FPT$ parameterized by bipartite treewidth. We provide the following complexity dichotomy when $H$ is a 2-connected graph, for each of $H$-Subgraph-Packing, $H$-Induced-Packing, $H$-Scattered-Packing, and $H$-Odd-Minor-Packing problem: if $H$ is bipartite, then the problem is para-NP-complete parameterized by bipartite treewidth while, if $H$ is non-bipartite, then it is solvable in XP-time. We define 1-${\cal H}$-treewidth by replacing the bipartite graph class by any class ${\cal H}$. Most of the technology developed here works for this more general parameter., Comment: Presented in IPEC 2023

In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9, by showing that Treewidth is NP-complete on cubic graphs.

We show that the $b$-Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathwidth is $W[t]$-hard for all $t$, and resolves the parameterized complexity of $b$-Coloring parameterized by treewidth.

We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the $st$-cut version of the problem is known to be NP-hard, the above global cut version is known to admit a quasi-polynomial randomized $n^{O(\log \mathrm{OPT})}$-time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as ``strong evidence that this problem is in P''. We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time $(np)^{o(\log n/ (\log \log n)^2)}$ would contradict the Exponential Time Hypothesis, where $n$ is the number of vertices, and $p$ is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is W[1]-hard when parameterized by the number of uncut labels. In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph. To turn this lower bound into a quasi-polynomial-time lower bound, we also needed to revisit the framework due to Marx [Theory Comput. 2010] of proving lower bounds assuming Exponential Time Hypothesis through the Subgraph Isomorphism problem parameterized by the number of edges of the pattern. Here, we provide an alternative simplified proof of the hardness of this problem that is more versatile with respect to the choice of the regimes of the parameters.

We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, $(s_2,t_2)$, and $(s_3,t_3)$, and an integer $k$, asks to find a set of at most $k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths, all $s_2t_2$-paths, and all $s_3t_3$-paths. The parameterized complexity of this case has been open since Chitnis, Cygan, Hajiaghayi, and Marx proved fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012, and Pilipczuk and Wahlstr\"{o}m proved the W[1]-hardness of the 4-terminal-pairs case at SODA 2016. On the technical side, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch, Pilipczuk, Wahlstr\"{o}m, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain.We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width, a recently introduced structural parameter [Bonnet, Kim, Thomass\'{e}, Watrigant, FOCS 2020]: By a recent characterization [Bonnet, Giocanti, Ossona de Mendes, Simon, Thomass\'{e}, Toru\'{n}czyk, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor, a vertex corresponding to the ``middle'' box in the grid minor can be proclaimed irrelevant -- not contained in the sought solution -- and thus reduced.

We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.

We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladder as an induced minor, then there exists a polynomial $p$ such that every $G \in \mathcal{G}$ contains at most $p(|V(G)|)$ minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from $\mathcal{G}$. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).

We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints ($\mathsf{A\&C~DN}$ for short) which extends existential $\mathsf{MSO_1}$ with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kant\'e, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed $\mathsf{A\&C~DN}$ formula is solvable in $n^{O(w)}$ time when the input graph is given together with a branch decomposition of mim-width $w$. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions. Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the $d$-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis ($\mathsf{ETH}$) for tree-width, clique-width and rank-width; the above mentioned run time for mim-width is nearly tight under the $\mathsf{ETH}$ for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-$\mathsf{NP}$-hard when parameterized by mim-width plus formula length.

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

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

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.

The CGMF code implements the Hauser-Feshbach statistical nuclear reaction model to follow the de-excitation of fission fragments by successive emissions of prompt neutrons and $\gamma$ rays. The Monte Carlo technique is used to facilitate the analysis of complex distributions and correlations among the prompt fission observables. Starting from initial configurations for the fission fragments in mass, charge, kinetic energy, excitation energy, spin, and parity, $Y(A,Z,KE,U,J,\pi)$, CGMF samples neutron and $\gamma$-ray probability distributions at each stage of the decay process, conserving energy, spin and parity. Nuclear structure and reaction input data from the RIPL library are used to describe fission fragment properties and decay probabilities. Characteristics of prompt fission neutrons, prompt fission gamma rays, and independent fission yields can be studied consistently. Correlations in energy, angle and multiplicity among the emitted neutrons and $\gamma$ rays can be easily analyzed as a function of the emitting fragments.

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph $G$ and an integer $k$, ask whether $G$ has two (maximum/perfect) matchings whose symmetric difference is at least $k$. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if $k$ is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by $k$. We round off the work by showing that Diverse Pair of Matchings has a kernel on $\mathcal{O}(k^2)$ vertices., Comment: To appear at ISAAC 2020

We present a measurement of the rate of correlated neutron captures in the WATCHBOY detector, deployed at a depth of approximately 390 meters water equivalent (m.w.e.) in the Kimballton Underground Research Facility (KURF). WATCHBOY consists of a cylindrical 2 ton water target doped with 0.1% gadolinium, surrounded by a 40 ton undoped water hermetic shield. We present a comparison of our results with the expected rate of correlated neutron captures arising from high-energy neutrons incident on the outside of the WATCHBOY shield, predicted by a hybrid FLUKA/GEANT4-based simulation. The incident neutron energy distribution used in the simulation was measured by a fast neutron spectrometer, the 1.8-ton Multiplicity and Recoil Spectrometer (MARS) detector, at the same depth. We find that the measured detection rate of two correlated neutrons is consistent with that predicted by simulation. The result lends additional confidence in the detection technique used by MARS, and therefore in the MARS spectra as measured at three different depths. Confirmation of the fast neutron flux and spectrum is important as it helps validate the scaling models used to predict the fast neutron fluxes at different overburdens., Comment: 11 pages, 16 figures, Phys. Rev. C (forthcoming)

A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with $q$ colors. For fixed $q \ge 2$, we give an $\mathcal{O}^{\star}(q^{tw})$-time algorithm when the input graph is given together with one of its tree decompositions of width $tw$. We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is XP parameterized by clique-width.

We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b-Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.

In this paper, we study a variant of hedonic games, called \textsc{Seat Arrangement}. The model is defined by a bijection from agents with preferences to vertices in a graph. The utility of an agent depends on the neighbors assigned in the graph. More precisely, it is the sum over all neighbors of the preferences that the agent has towards the agent assigned to the neighbor. We first consider the price of stability and fairness for different classes of preferences. In particular, we show that there is an instance such that the price of fairness ({\sf PoF}) is unbounded in general. Moreover, we show an upper bound $\tilde{d}(G)$ and an almost tight lower bound $\tilde{d}(G)-1/4$ of {\sf PoF}, where $\tilde{d}(G)$ is the average degree of an input graph. Then we investigate the computational complexity of problems to find certain ``good'' seat arrangements, say \textsc{Maximum Welfare Arrangement}, \textsc{Maximin Utility Arrangement}, \textsc{Stable Arrangement}, and \textsc{Envy-free Arrangement}. We give dichotomies of computational complexity of four \textsc{Seat Arrangement} problems from the perspective of the maximum order of connected components in an input graph. For the parameterized complexity, \textsc{Maximum Welfare Arrangement} can be solved in time $n^{O(\gamma)}$, while it cannot be solved in time $f(\gamma)^{o(\gamma)}$ under ETH, where $\gamma$ is the vertex cover number of an input graph. Moreover, we show that \textsc{Maximin Utility Arrangement} and \textsc{Envy-free Arrangement} are weakly NP-hard even on graphs of bounded vertex cover number. Finally, we prove that determining whether a stable arrangement can be obtained from a given arrangement by $k$ swaps is W[1]-hard when parameterized by $k+\gamma$, whereas it can be solved in time $n^{O(k)}$.

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.

It can be shown that each permutation group $G \sqsubseteq S_n$ can be embedded, in a well defined sense, in a connected graph with $O(n+|G|)$ vertices. Some groups, however, require much fewer vertices. For instance, $S_n$ itself can be embedded in the $n$-clique $K_n$, a connected graph with n vertices. In this work, we show that the minimum size of a context-free grammar generating a finite permutation group $G \sqsubseteq S_n$ can be upper bounded by three structural parameters of connected graphs embedding $G$: the number of vertices, the treewidth, and the maximum degree. More precisely, we show that any permutation group $G \sqsubseteq S_n$ that can be embedded into a connected graph with $m$ vertices, treewidth k, and maximum degree $\Delta$, can also be generated by a context-free grammar of size $2^{O(k\Delta\log\Delta)}\cdot m^{O(k)}$. By combining our upper bound with a connection between the extension complexity of a permutation group and the grammar complexity of a formal language, we also get that these permutation groups can be represented by polytopes of extension complexity $2^{O(k \Delta\log \Delta)}\cdot m^{O(k)}$. The above upper bounds can be used to provide trade-offs between the index of permutation groups, and the number of vertices, treewidth and maximum degree of connected graphs embedding these groups. In particular, by combining our main result with a celebrated $2^{\Omega(n)}$ lower bound on the grammar complexity of the symmetric group $S_n$ we have that connected graphs of treewidth $o(n/\log n)$ and maximum degree $o(n/\log n)$ embedding subgroups of $S_n$ of index $2^{cn}$ for some small constant $c$ must have $n^{\omega(1)}$ vertices. This lower bound can be improved to exponential on graphs of treewidth $n^{\varepsilon}$ for $\varepsilon<1$ and maximum degree $o(n/\log n)$.

We have calculated a complete set of primary fission fragment mass yields, $Y(A)$, for heavy nuclei across the chart of nuclides, including those of particular relevance to the rapid neutron capture process ($r$ process) of nucleosynthesis. We assume that the nuclear shape dynamics are strongly damped which allows for a description of the fission process via Brownian shape motion across nuclear potential-energy surfaces. The macroscopic energy of the potential was obtained with the Finite-Range Liquid-Drop Model (FRLDM), while the microscopic terms were extracted from the single-particle level spectra in the fissioning system by the Strutinsky procedure for the shell energies and the BCS treatment for the pairing energies. For each nucleus considered, the fission fragment mass yield, $Y(A)$, is obtained from 50,000 -- 500,000 random walks on the appropriate potential-energy surface. The full mass and charge yield, $Y(Z,A)$, is then calculated by invoking the Wahl systematics. With this method, we have calculated a comprehensive set of fission-fragment yields from over 3,800 nuclides bounded by $80\leq Z \leq 130$ and $A\leq330$; these yields are provided as an ASCII formatted database in the supplemental material. We compare our yields to known data and discuss general trends that emerge in low-energy fission yields across the chart of nuclides., Comment: 22 pages, 15 figures

In this work, we study the $d$-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of $r$ solutions of size at most $k$ each, which has recently been introduced to the field of parameterized complexity [Baste et al., 2019]. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process which models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are FPT in $k + r$ for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of `base' solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest., Comment: 17 pages, 3 figures

In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in $\mathcal{O}(n^2)$ time., Comment: 30 pages, 10 figures; accepted at STACS 2020

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter., Comment: Accepted to Twenty-Ninth International Joint Conference on Artificial Intelligence, {IJCAI} 2020, 16 pages

We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkovi\v{c} on the occasion of his 60th birthday. The Vertex Cover problem is often referred to as the Drosophila of parameterized complexity. It enjoys a long history. New and worthy perspectives will always be demonstrated first with concrete results here. This survey discusses several research directions in Vertex Cover kernelization. The Barrier Degree of Vertex Cover kernelization is discussed. We have reduction rules that kernelize vertices of small degree, including in this paper new results that reduce graphs almost to minimum degree five. Can this process go on forever? What is the minimum vertex-degree barrier for polynomial-time kernelization? Assuming the Exponential-Time Hypothesis, there is a minimum degree barrier. The idea of automated kernelization is discussed. We here report the first experimental results of an AI-guided branching algorithm for Vertex Cover whose logic seems amenable for application in finding reduction rules to kernelize small-degree vertices. The survey highlights a central open problem in parameterized complexity. Happy Birthday, Juraj!, Comment: 25 pages, 10 figures. Appeared in volume 11011 of LNCS, pages 330-356, see Reference [29] in the text. Compared to [29], this arXiv-upload contains a fixed version of Reduction R.8, the order of presentation of Reductions R.6 and R.7 has been switched, and a few observations have been added in Section 3

A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors. The $b$-chromatic number of a graph $G$, denoted by $\chi_b(G)$, is the maximum number $k$ such that $G$ admits a $b$-coloring with $k$ colors. We consider the complexity of the b-Coloring problem, whenever the value of $k$ is close to one of two upper bounds on $\chi_b(G)$: The maximum degree $\Delta(G)$ plus one, and the $m$-degree, denoted by $m(G)$, which is defined as the maximum number $i$ such that $G$ has $i$ vertices of degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k \in \{\Delta(G) + 1 - p, m(G) - p\}$, the problem is polynomial-time solvable whenever $p \in \{0, 1\}$ and, even when $k = 3$, it is NP-complete whenever $p \ge 2$. We furthermore consider parameterizations of the b-Coloring problem that involve the maximum degree $\Delta(G)$ of the input graph $G$ and give two FPT-algorithms. First, we show that deciding whether a graph $G$ has a $b$-coloring with $m(G)$ colors is FPT parameterized by $\Delta(G)$. Second, we show that b-Coloring is FPT parameterized by $\Delta(G) + \ell_k(G)$, where $\ell_k(G)$ denotes the number of vertices of degree at least $k$., Comment: 20 pages, 1 figure

We evaluate the impact of using sets of fission yields given by the GEF code for spontaneous (sf), neutron-induced ((n,f)), and beta-delayed (betadf) fission processes which take into account the approximate initial excitation energy of the fissioning compound nucleus. We further explore energy-dependent fission dynamics in the r process by considering the sensitivity of our results to the treatment of the energy sharing and de-excitation of the fission fragments using the FREYA code. We show that the asymmetric-to-symmetric yield trends predicted by GEF can reproduce the high-mass edge of the second r-process peak seen in solar data and examine the sensitivity of this result to the mass model and astrophysical conditions applied. We consider the effect of fission yields and barrier heights on the nuclear heating rates used to predict kilonova light curves. We find that fission barriers influence the contribution of 254Cf spontaneous fission to the heating at ~100 days, such that a light curve observation consistent with such late-time heating would both confirm that actinides were produced in the event and imply the fission barriers are relatively high along the 254Cf beta-feeding path. We lastly determine the key nuclei responsible for setting the r-process abundance pattern by averaging over thirty trajectories from a 1.2--1.4 M_odot neutron star merger simulation. We show it is largely the odd-N nuclei undergoing (Z,N)(n,f) and (Z,N)betadf that control the relative abundances near the second peak. We find the "hot spots" for beta-delayed and neutron-induced fission given all mass models considered and show most of these nuclei lie between the predicted N=184 shell closure and the location of currently available experimental decay data.

Neutron star mergers offer unique conditions for the creation of the heavy elements and additionally provide a testbed for our understanding of this synthesis known as the $r$-process. We have performed dynamical nucleosynthesis calculations and identified a single isotope, $^{254}$Cf, which has a particularly high impact on the brightness of electromagnetic transients associated with mergers on the order of 15 to 250 days. This is due to the anomalously long half-life of this isotope and the efficiency of fission thermalization compared to other nuclear channels. We estimate the fission fragment yield of this nucleus and outline the astrophysical conditions under which $^{254}$Cf has the greatest impact to the light curve. Future observations in the middle-IR which are bright during this regime could indicate the production of actinide nucleosynthesis., Comment: 9 pages, 5 figures

We generalize the family of $(\sigma, \rho)$-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-$r$ dominating set and distance-$r$ independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as $k$-trapezoid graphs, Dilworth $k$-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, $k$-polygon graphs, circular arc graphs, complements of $d$-degenerate graphs, and $H$-graphs if given an $H$-representation. To supplement these findings, we show that many classes of (distance) $(\sigma, \rho)$-problems are W[1]-hard parameterized by mim-width + solution size., Comment: Accepted at IPEC 2018

We have developed a Hauser-Feshbach fission fragment decay model, HF$^3$D, which can be applied to the statistical decay of more than 500 primary fission fragment pairs (1,000 nuclides) produced by the neutron induced fission of $^{235}$U. The fission fragment yield $Y(A)$ and the total kinetic energy TKE are model inputs, and we estimate them from available experimental data for the $^{235}$U(n$\rm_{th}$,f) system. The model parameters in the statistical decay calculation are adjusted to reproduce some fission observables, such as the neutron emission multiplicity $\overline{\nu}$, its distribution $P(\nu)$, and the mass dependence $\overline\nu(A)$. The calculated fission product yield and isomeric ratio are compared with experimental data. We show that the calculated independent fission product yield $Y_I(A)$ at the thermal energy reproduces the experimental data well, while the calculated isomeric ratios tend to be lower than the Madland-England model prediction. The model is extended to higher incident neutron energies up to the second chance fission threshold. We demonstrate for the first time that most of the isomeric ratios stay constant, although the production of isomeric state itself changes as the incident energy increases.

The Hauser-Feshbach statistical model is applied to the de-excitation of primary fission fragments using input mass yields calculated with macroscopic-microscopic models of the potential energy surface. We test the sensitivity of the prompt fission observables to the input mass yields for two important reactions, $^{235}$U$(n_\mathrm{th},f)$ and $^{239}$Pu$(n_\mathrm{th},f)$, for which good experimental data exist. General traits of the mass yields, such as the location of the peaks and their widths, can impact both the prompt neutron and $\gamma$-ray multiplicities, as well as their spectra. Specifically, we use several mass yields to determine a linear correlation between the calculated prompt neutron multiplicity $\bar{\nu}$ and the average heavy-fragment mass $\langle A_h\rangle$ of the input mass yields $\partial\bar{\nu}/\partial\langle A_h\rangle = \pm 0.1\,n/f/\mathrm{u}$. The mass peak width influences the correlation between the total kinetic energy of the fission fragments and the total number of prompt neutrons emitted $\bar{\nu}_T(\mathrm{TKE})$. Typical biases on prompt particle observables from using calculated mass yields instead of experimental ones are: $\delta \bar{\nu} = 4\%$ for the average prompt neutron multiplicity, $\delta \bar{M}_\gamma = 1\%$ for the average prompt $\gamma$-ray multiplicity, $\delta \bar{\epsilon}_n^\mathrm{LAB} = 1\%$ for the average outgoing neutron energy, $\delta \bar{\epsilon}_\gamma = 1\%$ for the average $\gamma$-ray energy, and $\delta \langle\mathrm{TKE}\rangle = 0.4\%$ for the average total kinetic energy of the fission fragments., Comment: 12 pages, 8 figures, 2 tables

We complement the recent algorithmic result that Feedback Vertex Set is XP-time solvable parameterized by the mim-width of a given branch decomposition of the input graph [3] by showing that the problem is W[1]-hard in this parameterization. The hardness holds even for linear mim-width, as well as for H-graphs, where the parameter is the number of edges in H. To obtain this result, we adapt a reduction due to Fomin, Golovach and Raymond [2], following the same line of reasoning but adding a new gadget., Comment: 7 pages, 3 figures

We give a first polynomial-time algorithm for (Weighted) Feedback Vertex Set on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width $w$, we give an $n^{\mathcal{O}(w)}$-time algorithm that solves Feedback Vertex Set. This provides a unified algorithm for many well-known classes, such as Interval graphs and Permutation graphs, and furthermore, it gives the first polynomial-time algorithms for other classes of bounded mim-width, such as Circular Permutation and Circular $k$-Trapezoid graphs for fixed $k$. In all these classes the decomposition is computable in polynomial time, as shown by Belmonte and Vatshelle [Theor. Comput. Sci. 2013]. We show that powers of graphs of tree-width $w - 1$ or path-width $w$ and powers of graphs of clique-width $w$ have mim-width at most $w$. These results extensively provide new classes of bounded mim-width. We prove a slight strengthening of the first statement which implies that, surprisingly, Leaf Power graphs which are of importance in the field of phylogenetic studies have mim-width at most $1$. Given a tree decomposition of width $w-1$, a path decomposition of width $w$, or a clique-width $w$-expression of a graph, one can for any value of $k$ find a mim-width decomposition of its $k$-power in polynomial time, and apply our algorithm to solve Feedback Vertex Set on the $k$-power in time $n^{\mathcal{O}(w)}$. In contrast to Feedback Vertex Set, we show that Hamiltonian Cycle is NP-complete even on graphs of linear mim-width $1$, which further hints at the expressive power of the mim-width parameter., Comment: 26 pages, 3 figures; accepted at STACS 2018

Detailed information on the fission process can be inferred from the observation, modeling and theoretical understanding of prompt fission neutron and $\gamma$-ray~observables. Beyond simple average quantities, the study of distributions and correlations in prompt data, e.g., multiplicity-dependent neutron and \gray~spectra, angular distributions of the emitted particles, $n$-$n$, $n$-$\gamma$, and $\gamma$-$\gamma$~correlations, can place stringent constraints on fission models and parameters that would otherwise be free to be tuned separately to represent individual fission observables. The FREYA~and CGMF~codes have been developed to follow the sequential emissions of prompt neutrons and $\gamma$-rays~from the initial excited fission fragments produced right after scission. Both codes implement Monte Carlo techniques to sample initial fission fragment configurations in mass, charge and kinetic energy and sample probabilities of neutron and $\gamma$~emission at each stage of the decay. This approach naturally leads to using simple but powerful statistical techniques to infer distributions and correlations among many observables and model parameters. The comparison of model calculations with experimental data provides a rich arena for testing various nuclear physics models such as those related to the nuclear structure and level densities of neutron-rich nuclei, the $\gamma$-ray~strength functions of dipole and quadrupole transitions, the mechanism for dividing the excitation energy between the two nascent fragments near scission, and the mechanisms behind the production of angular momentum in the fragments, etc. Beyond the obvious interest from a fundamental physics point of view, such studies are also important for addressing data needs in various nuclear applications. (See text for full abstract.), Comment: 39 pages, 57 figure files, published in Eur. Phys. J. A, reference added this version

We present a self-consistency analysis of fission product yield evaluations. Anomalous yields are determined using a series of simple conservation checks and comparing charge distributions with common parameterizations. The total prompt neutron multiplicity as a function of product mass $\bar{\nu}_T(A)$ is derived directly from the independent fission product yields using average charge conservation. This method is checked against Monte Carlo simulations of the de-excitation of the fission fragments in a Hauser-Feshbach statistical decay framework. The derived $\bar{\nu}_T(A)$ is compared with experimental data, when available, and used to compare the prompt neutron multiplicity $\bar{\nu}$ for the various evaluations. Differences in $\bar{\nu}$ for each evaluation are investigated and possible sources are identified. We also identify fission reactions that are inconsistent with prompt neutron data and propose possible solutions to remedy the observed inconsistencies., Comment: 6 pages, 5 figures, 1 table

We give the first polynomial-time algorithms on graphs of bounded maximum induced matching width (mim-width) for problems that are not locally checkable. In particular, we give $n^{\mathcal{O}(w)}$-time algorithms on graphs of mim-width at most $w$, when given a decomposition, for the following problems: Longest Induced Path, Induced Disjoint Paths and $H$-Induced Topological Minor for fixed $H$. Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc, Permutation and Circular Permutation graphs, Convex graphs, $k$-Trapezoid, Circular $k$-Trapezoid, $k$-Polygon, Dilworth-$k$ and Co-$k$-Degenerate graphs for fixed $k$., Comment: 20 pages, 4 figures; accepted at IPEC 2017

We test common fluence diagnostics in the regime of very low burnup natural uranium reactor samples. The fluence diagnostics considered are the uranium isotopics ratios $^{235}$U/$^{238}$U and $^{236}$U/$^{235}$U, for which we find simple analytic formulas agree well with full reactor simulation predictions. Both ratios agree reasonably well with one another for fluences in the mid $10^{19}\,\mathrm{n/cm^2}$ range. However, below about $10^{19}\,\mathrm{n/cm^2}$ the concentrations of $^{236}$U are found to be sufficiently low that the measured $^{236}$U/$^{235}$U ratios become unreliable. We also derive and test diagnostics for determining sample cooling times in situations where very low burnup and very long cooling times render many standard diagnostics, such as the $^{241}$Am/$^{241}$Pu ratio, impractical. We find that using several fragment ratios are necessary to detect the presence of systematic errors, such as fractionation., Comment: 7 pages, 4 figures

The $q$-Coloring problem asks whether the vertices of a graph can be properly colored with $q$ colors. Lokshtanov et al. [SODA 2011] showed that $q$-Coloring on graphs with a feedback vertex set of size $k$ cannot be solved in time $\mathcal{O}^*((q-\varepsilon)^k)$, for any $\varepsilon > 0$, unless the Strong Exponential-Time Hypothesis (SETH) fails. In this paper we perform a fine-grained analysis of the complexity of $q$-Coloring with respect to a hierarchy of parameters. We show that even when parameterized by the vertex cover number, $q$ must appear in the base of the exponent: Unless ETH fails, there is no universal constant $\theta$ such that $q$-Coloring parameterized by vertex cover can be solved in time $\mathcal{O}^*(\theta^k)$ for all fixed $q$. We apply a method due to Jansen and Kratsch [Inform. & Comput. 2013] to prove that there are $\mathcal{O}^*((q - \varepsilon)^k)$ time algorithms where $k$ is the vertex deletion distance to several graph classes $\mathcal{F}$ for which $q$-Coloring is known to be solvable in polynomial time. We generalize earlier ad-hoc results by showing that if $\mathcal{F}$ is a class of graphs whose $(q+1)$-colorable members have bounded treedepth, then there exists some $\varepsilon > 0$ such that $q$-Coloring can be solved in time $\mathcal{O}^*((q-\varepsilon)^k)$ when parameterized by the size of a given modulator to $\mathcal{F}$. In contrast, we prove that if $\mathcal{F}$ is the class of paths - some of the simplest graphs of unbounded treedepth - then no such algorithm can exist unless SETH fails., Comment: 17 pages, 2 figures

We investigate the ability of an antineutrino detector to determine the fuel type of a reactor. A hypothetical 5t antineutrino detector is placed 25m from the core and measures the spectral shape and rate of antineutrinos emitted by fission fragments in the core for a number of 90 day periods. Our results indicate that four major fuel types can be differentiated from the variation of fission fractions over the irradiation time with a true positive probability of detection at 95%. In addition, we demonstrate that antineutrinos can identify the burn-up at which weapons-grade mixed-oxide (MOX) fuel would be reduced to reactor-grade MOX on average, providing assurance that plutonium disposition goals are met. In addition, we investigate removal scenarios where plutonium is purposefully diverted from a mixture of MOX and low-enriched uranium (LEU) fuel. Finally, we discuss how our analysis is impacted by a spectral distortion around 6MeV observed in the antineutrino spectrum measured from commercial power reactors., Comment: 6 pages, 3 figures

A measurement of electron antineutrino oscillation by the Daya Bay Reactor Neutrino Experiment is described in detail. Six 2.9-GW$_{\rm th}$ nuclear power reactors of the Daya Bay and Ling Ao nuclear power facilities served as intense sources of $\overline{\nu}_{e}$'s. Comparison of the $\overline{\nu}_{e}$ rate and energy spectrum measured by antineutrino detectors far from the nuclear reactors ($\sim$1500-1950 m) relative to detectors near the reactors ($\sim$350-600 m) allowed a precise measurement of $\overline{\nu}_{e}$ disappearance. More than 2.5 million $\overline{\nu}_{e}$ inverse beta decay interactions were observed, based on the combination of 217 days of operation of six antineutrino detectors (Dec. 2011--Jul. 2012) with a subsequent 1013 days using the complete configuration of eight detectors (Oct. 2012--Jul. 2015). The $\overline{\nu}_{e}$ rate observed at the far detectors relative to the near detectors showed a significant deficit, $R=0.949 \pm 0.002(\mathrm{stat.}) \pm 0.002(\mathrm{syst.})$. The energy dependence of $\overline{\nu}_{e}$ disappearance showed the distinct variation predicted by neutrino oscillation. Analysis using an approximation for the three-flavor oscillation probability yielded the flavor-mixing angle $\sin^22\theta_{13}=0.0841 \pm 0.0027(\mathrm{stat.}) \pm 0.0019(\mathrm{syst.})$ and the effective neutrino mass-squared difference of $\left|{\Delta}m^2_{\mathrm{ee}}\right|=(2.50 \pm 0.06(\mathrm{stat.}) \pm 0.06(\mathrm{syst.})) \times 10^{-3}\ {\rm eV}^2$. Analysis using the exact three-flavor probability found ${\Delta}m^2_{32}=(2.45 \pm 0.06(\mathrm{stat.}) \pm 0.06(\mathrm{syst.})) \times 10^{-3}\ {\rm eV}^2$ assuming the normal neutrino mass hierarchy and ${\Delta}m^2_{32}=(-2.56 \pm 0.06(\mathrm{stat.}) \pm 0.06(\mathrm{syst.})) \times 10^{-3}\ {\rm eV}^2$ for the inverted hierarchy., Comment: 44 pages, 44 figures