Search

We study an inverse problem of determining a time-dependent damping coefficient and potential appearing in the wave equation in a compact Riemannian manifold of dimension three or higher. More specifically, we are concerned with the case of conformally transversally anisotropic manifolds, or in other words, compact Riemannian manifolds with boundary conformally embedded in a product of the Euclidean line and a transversal manifold. With an additional assumption of the attenuated geodesic ray transform being injective on the transversal manifold, we prove that the knowledge of a certain partial Cauchy data set determines the time-dependent damping coefficient and potential uniquely. [ABSTRACT FROM AUTHOR]

Given a bipartite graph H = (V = VA ∪ VB, E) in which any vertex in VA (resp., VB) has degree at most DA (resp., DB), suppose there is a partition of V that is a refinement of the bipartition VA ∪ VB such that the parts in VA (resp., VB) have size at least KA (resp., kB). We prove that the condition DA/kB + DB/kA ≤ 1 is sufficient for the existence of an independent set of vertices of H that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos. [ABSTRACT FROM AUTHOR]

Fix k > 0, and let G be a graph, with vertex set partitioned into k subsets ("blocks") of approximately equal size. An induced subgraph of G is "transversal" (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A "pure pair" in G is a pair X,Y of disjoint subsets of V (G) such that either all edges between X,Y are present or none are; and in the present context we are interested in pure pairs (X,Y) where each of X,Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded. [ABSTRACT FROM AUTHOR]

The transversal number Τ (H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then Τ(H) < 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture. [ABSTRACT FROM AUTHOR]

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family\scrF. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTASs) for planar input graphs G, using a variety of techniques like the shifting technique [B. S. Baker, J. ACM, 41 (1994), pp. 153--180], bidimensionality [F. V. Fomin et al., Bidimensionality and EPTAS, in Proceedings of SODA 2011, ACM, New York, SIAM, Philadelphia, 2011, pp. 748--759], or connectivity domination [V. Cohen-Addad et al., Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of STOC 2016, ACM, New York, 2016, pp. 584--597]. These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the Even Cycle Transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini, Joret, and Pietropaoli [Hitting diamonds and growing cacti, in Proceedings of IPCO 2010, Lecture Notes in Comput. Sci. 6080, Springer, Berlin, 2010, pp. 191--204] showed that the integrality gap of the standard covering LP relaxation is\Theta (log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7\approx 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap upper bound of the same value for the standard LP relaxation on node-weighted planar graphs. [ABSTRACT FROM AUTHOR]

We prove that if a family of compact connected sets in the plane has the property that every three members of it are intersected by a line, then there are three lines intersecting all the sets in the family. This answers a question of Eckhoff [Discrete Comput. Geom., 9 (1993), pp. 203--214], who proved that, under the same condition, there are four lines intersecting all the sets. In fact, we prove a colorful version of this result under weakened conditions on the sets. Three sets A,B,C form a tight triple if conv(A\cup B) \cap conv(A\cup C) \cap conv(B \cap C) \not = \emptyset. This notion was first introduced by Holmsen, who showed that if \scrF is a family of compact convex sets in the plane in which every three sets form a tight triple, then there is a line intersecting at least 1 8 | \scrF | members of \scrF. Here we prove that if \scrF 1,. .. ,\scrF 6 are families of compact connected sets in the plane such that every three sets, chosen from three distinct families \scrF i, form a tight triple, then there exists 1 \leq j \leq 6 and three lines intersecting every member of \scrF j. In particular, this improves 1 8 to 1 3 in Holmsen's result. [ABSTRACT FROM AUTHOR]

We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that for every s \geq 1, both problems are polynomial-time solvable for sP3-free graphs and (sP1 + P5)-free graphs; here, the graph sP3 denotes the disjoint union of s paths on three vertices and the graph sP1 + P5 denotes the disjoint union of s isolated vertices and a path on five vertices. Our new results for Feedback Vertex Set extend all known polynomial-time results for Feedback Vertex Set on H-free graphs, namely for sP2-free graphs [Chiarelli et al., Theoret. Comput. Sci., 705 (2018), pp. 75--83], (sP1+P3)-free graphs [Dabrowski et al., Algorithmica, 82 (2020), pp. 2841--2866] and P5-free graphs [Abrishami et al., Induced subgraphs of bounded treewidth and the container method, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2021, pp. 1948--1964]. Together, the new results also show that both problems exhibit the same behavior on H-free graphs (subject to some open cases). This is in part due to a new general algorithm we design for finding in a (sP3)-free or (sP1 + P5)-free graph G a largest induced subgraph whose blocks belong to some finite class \scrC of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs. [ABSTRACT FROM AUTHOR]

We study inverse boundary problems for first order perturbations of the biharmonic operator on a conformally transversally anisotropic Riemannian manifold of dimension n ≥ 3. We show that a continuous first order perturbation can be determined uniquely from the knowledge of the set of the Cauchy data on the boundary of the manifold provided that the geodesic X-ray transform on the transversal manifold is injective. [ABSTRACT FROM AUTHOR]

We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs [Pilipczuk et al., ACM Trans. Algorithms, 14 (2018), 53]. It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem. [ABSTRACT FROM AUTHOR]

We study the Max Partial $H$-Coloring problem: given a graph $G$, find the largest induced subgraph of $G$ that admits a homomorphism into $H$, where $H$ is a fixed pattern graph without loops. Note that when $H$ is a complete graph on $k$ vertices, the problem reduces to finding the largest induced $k$-colorable subgraph, which for $k=2$ is equivalent (by complementation) to Odd Cycle Transversal. We prove that for every fixed pattern graph $H$ without loops, Max Partial $H$-Coloring can be solved in $\{P_5,F\}$-free graphs in polynomial time, whenever $F$ is a threshold graph; in $\{P_5,{bull}\}$-free graphs in polynomial time; in $P_5$-free graphs in time $n^{\mathcal{O}(\omega(G))}$; and in $\{P_6,{1-subdivided claw}\}$-free graphs in time $n^{\mathcal{O}(\omega(G)^3)}$. Here, $n$ is the number of vertices of the input graph $G$ and $\omega(G)$ is the maximum size of a clique in $G$. Furthermore, by combining the mentioned algorithms for $P_5$-free and for $\{P_6,{1-subdivided claw}\}$-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for Max Partial $H$-Coloring in these classes of graphs. Finally, we show that even a restricted variant of Max Partial $H$-Coloring is $\mathsf{NP}$-hard in the considered subclasses of $P_5$-free graphs if we allow loops on $H$. [ABSTRACT FROM AUTHOR]

We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of whether connected graphs admit longest path transversals of constant size. The same technique allows us to show that 2-connected graphs admit sublinear longest cycle transversals. [ABSTRACT FROM AUTHOR]

When dynamical systems that produce rhythmic behaviors operate within hard limits, they may exhibit limit cycles with sliding components, that is, closed isolated periodic orbits that make and break contact with a constraint surface. Examples include heel-ground interaction in locomotion, firing rate rectification in neural networks, and stick-slip oscillators. In many rhythmic systems, robustness against external perturbations involves response of both the shape and the timing of the limit cycle trajectory. The existing methods of infinitesimal phase response curve (iPRC) and variational analysis are well established for quantifying changes in timing and shape, respectively, for smooth systems. These tools have recently been extended to nonsmooth dynamics with transversal crossing boundaries. In this work, we further extend the iPRC method to nonsmooth systems with sliding components, which enables us to make predictions about the synchronization properties of weakly coupled stick-slip oscillators. We observe a new feature of the isochrons in a planar limit cycle with hard sliding boundaries: a nonsmooth kink in the asymptotic phase function, originating from the point at which the limit cycle smoothly departs the constraint surface and propagating away from the hard boundary into the interior of the domain. Moreover, the classical variational analysis neglects timing information and is restricted to instantaneous perturbations. By defining the "infinitesimal shape response curve" (iSRC), we incorporate timing sensitivity of an oscillator to describe the shape response of this oscillator to parametric perturbations. In order to extract timing information, we also develop a "local timing response curve" (lTRC) that measures the timing sensitivity of a limit cycle within any given region. We demonstrate in a specific example that taking into account local timing sensitivity in a nonsmooth system greatly improves the accuracy of the iSRC over the global timing analysis given by the iPRC. [ABSTRACT FROM AUTHOR]

Motivated by the successful application of geometry to proving the Harary-Hill conjecture for "pseudolinear"" drawings of Kn, we introduce "pseudospherical"" drawings of graphs. A spherical drawing of a graph G is a drawing in the unit sphere S2 in which the vertices of G are represented as points---no three on a great circle---and the edges of G are shortest-arcs in S2 connecting pairs of vertices. Such a drawing has three properties: (1) every edge e is contained in a simple closed curve gamma e such that the only vertices in gamma e are the ends of e; (2) if e not = f, then gamma e cap gamma f has precisely two crossings; and (3) if e not = f, then e intersects gamma f at most once, in either a crossing or an end of e. We use properties (1)--(3) to define a pseudospherical drawing of G. Our main result is that for the complete graph, properties (1)--(3) are equivalent to the same three properties but with "precisely two crossings"" in (2) replaced by "at most two crossings."" The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs (coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of K10 that has no extension to an arrangement of pseudocircles and a drawing of K9 that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice. [ABSTRACT FROM AUTHOR]

Solutions to optimization problems involving the numerical radius often belong to the class of "disk matrices"": those whose field of values is a circular disk in the complex plane centered at zero. We investigate this phenomenon using the variational-analytic idea of partial smoothness. We give conditions under which the set of disk matrices is locally a manifold M, with respect to which the numerical radius r is partly smooth, implying that r is smooth when restricted to M but strictly nonsmooth when restricted to lines transversal to M. Consequently, minimizers of the numerical radius of a parametrized matrix often lie in M. Partial smoothness holds, in particular, at n Ã-- n matrices with exactly n-1 nonzeros, all on the superdiagonal. On the other hand, in the real 18-dimensional vector space of complex 3 Ã-- 3 matrices, the disk matrices comprise the closure of a semialgebraic manifold L with dimension 12, and the numerical radius is partly smooth with respect to L. [ABSTRACT FROM AUTHOR]

Let k, d, λ ≥ 1 be integers with d ≥ λ and let X be a finite set of points in Rd. A (d-λ)-plane L transversal to the convex hulls of all k-sets of X is called a Kneser transversal. If in addition L contains (d-λ) + 1 points of X, then L is called a complete Kneser transversal. In this paper, we present various results on the existence of (complete) Kneser transversals for λ = 2, 3. In order to do this, we introduce the notions of stability and instability for (complete) Kneser transversals. We first give a stability result for collections of d+2(k-λ) points in Rd with k-λ ≥ 2 and λ = 2, 3. We then present a description of Kneser transversals L of collections of d + 2(k - λ) points in Rd with k-λ ≥ 2 for λ = 2, 3. We show that either L is a complete Kneser transversal or it contains d-2(λ-1) points and the remaining 2(k-1) points of X are matched in k-1 pairs in such a way that L intersects the corresponding closed segments determined by them. The latter leads to new upper and lower bounds (in the case when λ = 2 and 3) for m(k, d, λ) defined as the maximum positive integer n such that every set of n points (not necessarily in general position) in Rd admit a Kneser transversal. Finally, by using oriented matroid machinery, we present some computational results (closely related to the stability and unstability notions). We determine the existence of (complete) Kneser transversals for each of the 246 different order types of configurations of 7 points in R3. [ABSTRACT FROM AUTHOR]

The paper treats a reaction-diffusion equation with hysteretic nonlinearity on a onedimensional lattice. It arises as a result of the spatial discretization of the corresponding continuous model with so-called nontransverse initial data and exhibits a propagating microstructure—which we call rattling—in the hysteretic component of the solution. We analyze this microstructure and determine the speed of its propagation depending on the parameters of hysteresis and the nontransversality coefficient in the initial data. [ABSTRACT FROM AUTHOR]

Subspace clustering is the problem of clustering data that lie close to a union of linear subspaces. Existing algebraic subspace clustering methods are based on fitting the data with an algebraic variety and decomposing this variety into its constituent subspaces. Such methods are well suited to the case of a known number of subspaces of known and equal dimensions, where a single polynomial vanishing in the variety is sufficient to identify the subspaces. While subspaces of unknown and arbitrary dimensions can be handled using multiple vanishing polynomials, current approaches are not robust to corrupted data due to the difficulty of estimating the number of polynomials. As a consequence, the current practice is to use a single polynomial to fit the data with a union of hyperplanes containing the union of subspaces, an approach that works well only when the dimensions of the subspaces are high enough. In this paper, we propose a new algebraic subspace clustering algorithm, which can identify the subspace S passing through a point X by constructing a descending filtration of subspaces containing S. First, a single polynomial vanishing in the variety is identified and used to find a hyperplane containing S. After intersecting this hyperplane with the variety to obtain a subvariety, a new polynomial vanishing in the subvariety is found, and so on, until no nontrivial vanishing polynomial exists. In this case, our algorithm identifies S as the intersection of the hyperplanes identified thus far. By repeating this procedure for other points, our algorithm eventually identifies all the subspaces. Alternatively, by constructing a filtration at each data point and comparing any two filtrations using a suitable affinity, we propose a spectral version of our algebraic procedure based on spectral clustering, which is suitable for computations with noisy data. We show by experiments on synthetic and real data that the proposed algorithm outperforms state-of-the-art methods on several occasions, thus demonstrating the merit of the idea of filtrations. [ABSTRACT FROM AUTHOR]

The 3/4 -Game Total Domination Conjecture posed by Henning, Klavžar, and Rall [Combinatorica, (2016)] states that if G is a graph on n vertices in which every component contains at least three vertices, then γtg(G) ≤ 3/4n, where γtg(G) denotes the game total domination number of G. Motivated by this conjecture, we raise the problem to a higher level by introducing a transversal game in hypergraphs. We define the game transversal number, τg(H), of a hypergraph H, and prove that if every edge of H has size at least 2, and H ... C4, then τg(H) ≤ 4/11 (nH + mH), where nH and mH denote the number of vertices and edges, respectively, in H. Further, we characterize the hypergraphs achieving equality in this bound. As an application of this result, we prove that if G is a graph on n vertices with minimum degree at least 2, then γtg(G) < 8 11n. As a consequence of this result, the 3/4 -Game Total Domination Conjecture is true over the class of graphs with minimum degree at least 2. [ABSTRACT FROM AUTHOR]

Given a simple undirected graph G and a positive integer s, the maximum vertex coverage problem (MVC) is the problem of finding a set U of s vertices of G such that the number of edges having at least one endpoint in U is as large as possible. The problem is NP-hard even in bipartite graphs, as shown in two recent papers [N. Apollonio and B. Simeone, Discrete Appl. Math., 165 (2014), pp. 37-48; G. Joret and A. Vetta, Reducing the Rank of a Matroid, preprint, arXiv:1211.4853v1 [cs.DS], 2012]. By exploiting the structure of the fractional optimal solutions of a linear programming formulation for the maximum coverage problem, we provide a 4/5-approximation algorithm for the problem. The algorithm immediately extends to the weighted version of MVC. [ABSTRACT FROM AUTHOR]

The Alon--Tarsi Latin squares conjecture is extended to odd dimensions by stating it for reduced Latin squares (Latin squares having the identity permutation as their first row and first column). Using a modified version of an identity proved by Onn [Amer. Math. Monthly, 104 (1997), pp. 156-159], we show that the validity of this conjecture implies a weak version of Rota's bases conjecture for odd dimensions, namely that a set of n bases in ℝn n - 1 disjoint independent transversals. [ABSTRACT FROM AUTHOR]

The BIPARTITE CONTRACTION problem takes as input an n-vertex graph G and an integer κ, and the task is to determine whether we can obtain a bipartite graph from G by a sequence of at most κ edge contractions. We show that BIPARTITE CONTRACTION is fixed-parameter tractable when parameterized by κ. Despite a strong resemblance between Bipartite Contraction and the classical ODD CYCLE TRANSVERSAL (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to BIPARTITE CONTRACTION. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertices, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique. [ABSTRACT FROM AUTHOR]