Search

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 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]

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]

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 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]