Search

This paper deals with a problem from computational convexity and its application to computer algebra. This paper determines the complexity of computing the Minkowski sum of k convex polytopes in $\mathbb{R}^d $, which are presented either in terms of vertices or in terms of facets. In particular, if the dimension d is fixed, the authors obtain a polynomial time algorithm for adding k polytopes with up to n vertices. The second part of this paper introduces dynamic versions of Buchberger’s Grobner bases algorithm for polynomial ideals. Using the Minkowski addition of Newton polytopes, the authors show that the following problem can be solved in polynomial time for any finite set of polynomials $\mathcal{T} \subset K [ x_1 , \ldots ,x_d ]$, where d is fixed: Does there exist a term order $\tau $ such that $\mathcal{T}$ is a Grobner basis for its ideal with respect to $\tau $? If not, find an optimal term order for $\mathcal{T}$ with respect to a natural Hilbert function criterion.

This paper is concerned with pair-splitting sets in $AG_k ( m,q )$, the design obtained from the points and k-flats in $AG (m,q)$. A pair-splitting set is a set of parallel classes $\{ R_1 ,R_2 , \cdots ,R_s \}$ such that there is no pair of distinct points $a,b$ such that $a,b$ are contained in a common k-flat of each of the s parallel classes. It is easy to prove that a lower bound on s is $\lceil m/( m - k ) \rceil $. The main result of this paper is to prove that this lower bound is always achievable for any choice of $m,q$, and k, where $0\leqq k\leqq m - 1$. The concept of pair-splitting sets arises naturally out of the problem of finding roots in $GF( q^m )$ of a polynomial over $GF ( q^m )$. The connection between the two concepts is briefly discussed.

This paper presents a family of memory-balanced routing schemes that use relatively short paths while storing relatively little routing information. The quality of the routes provided by a scheme is measured in terms of their stretch, namely, the maximum ratio between the length of a route connecting some pair of processors and their distance. The hierarchical schemes$\mathcal{H}_k $ (for every integer $k\geqq 1$) presented in this paper guarantee a stretch factor of $O( k^2 )$ on the length of the routes and require storing at most $O( k \cdot n^{1/k} \cdot \log n\log D )$ bits of routing information per vertex in an n-processor network with diameter D. The schemes are name independent and applicable to general networks with arbitrary edge weights. This improves on previous designs whose stretch bound was exponential in k.The proposed schemes are based on a new efficient solution to a certain graph-theoretic problem concerning sparse graph covers. The new cover technique has already found several other a...

This paper studies the fundamental relations among integer flows, modulo orientations, integer-valued and real-valued circular flows, and monotonicity of flows in signed graphs. A (signed) graph is...

In this paper we show examples for applications of the Bombieri-Lang conjecture in additive combinatorics, giving bounds on the cardinality of sumsets of squares and higher powers of integers. Using similar methods we give bounds on the sum-product problem for matchings., Comment: 14 pages

Let $P_G(k)$ be the number of proper $k$-colorings of a finite simple graph $G$. Tomescu's conjecture, which was recently solved by Fox, He, and Manners, states that $P_G(k) \le k!(k-1)^{n-k}$ for all connected graphs $G$ on $n$ vertices with chromatic number $k\geq 4$. In this paper, we study the same problem with the additional constraint that $G$ is $\ell$-connected. For $2$-connected graphs $G$, we prove a tight bound \[ P_G(k) \le (k-1)!((k-1)^{n-k+1} + (-1)^{n-k}), \] and show that equality is only achieved if $G$ is a $k$-clique with an ear attached. For $\ell \ge 3$, we prove an asymptotically tight upper bound \[ P_G(k) \le k!(k-1)^{n-\ell - k + 1} + O((k-2)^n), \] and provide a matching lower bound construction. For the ranges $k \geq \ell$ or $\ell \geq (k-2)(k-1)+1$ we further find the unique graph maximizing $P_G(k)$. We also consider generalizing $\ell$-connected graphs to connected graphs with minimum degree $\delta$.

In this paper we go one step further in the automatic generation of FPTASes for multistage stochastic dynamic programs with scalar state and action spaces, in which the cost-to-go functions have a ...

Submodularity is one of the most important properties in combinatorial optimization, and $k$-submodularity is a generalization of submodularity. Maximization of a $k$-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained $k$-submodular maximization, Iwata et al. gave randomized $k/(2k-1)$-approximation algorithm for monotone functions, and randomized $1/2$-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives $\frac{k^2+1}{2k^2+1}$-approximation for $k\geq 3$. We also give a randomized $\frac{\sqrt{17}-3}{2}$-approximation algorithm for $k=3$. We use the same framework used in Iwata et al. and Ward and \v{Z}ivn\'{y} with different probabilities., Comment: 22 pages,3 figures

Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, different clusterings of the same data set become relevant. For example, different algorithms for the same clustering task may return dramatically different solutions. We are interested in applications in which one clustering has to be transformed into another; e.g., when a gradual transition from an old solution to a new one is required. In this paper, we devise methods for constructing such a transition based on linear programming and network theory. We use a so-called clustering-difference graph to model the desired transformation and provide methods for decomposing the graph into a sequence of elementary moves that accomplishes the transformation. These moves are equivalent to the edge directions, or circuits, of the underlying partition polytopes. Therefore, in addition to a conceptually new metric for measuring the distance between clusterings, we provide new bounds on the circuit diameter of these partition polytopes.

Given a large graph H, does the binomial random graph G(n, p) contain a copy of H as an induced subgraph with high probability? This classical question has been studied extensively for various graphs H, going back to the study of the independence number of G(n, p) by Erdos and Bollobas and by Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if C/n

In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. We design a meta-algorithm that solves all these problems and whose running time is upper bounded by $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$, and $n^{O(k)}$ where $k$ is respectively the clique-width, $\mathbb{Q}$-rank-width, rank-width, and maximum induced matching width of a given decomposition. Our approach simplifies and unifies the known algorithms for each of the parameters and its running time matches asymptotically also the running times of the best known algorithms for basic \sf NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the $d$-neighbor equivalence defined in [B. Bui-Xuan, J. A. Telle, and M. Vatshelle, Theoret. Comput. Sci., (2013), pp. 66--76] and the rank-based approach introduced in [H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof, Inform. and Comput., 243 (2015), pp. 86--111]. The results we obtain highlight the importance of the $d$-neighbor equivalence relation on the algorithmic applications of width measures. We also prove that our framework could be useful for ${\sf W}[1]$-hard problems parameterized by clique-width such as Max Cut and Maximum Minimal Cut. For these latter problems, we obtain $n^{O(k)}$, $n^{O(k)}$, and $n^{2^{O(k)}}$ time algorithms where $k$ is respectively the clique-width, the $\mathbb{Q}$-rank-width, and the rank-width of the input graph. publishedVersion

Let $B_n^{(k)}$ be the book graph which consists of $n$ copies of $K_{k+1}$ all sharing a common $K_k$, and let $C_m$ be a cycle of length $m$. In this paper, we first determine the exact value of $r(B_n^{(2)}, C_m)$ for $\frac{8}{9}n+112\le m\le \lceil\frac{3n}{2}\rceil+1$ and $n \geq 1000$. This answers a question of Faudree, Rousseau and Sheehan (Cycle--book Ramsey numbers, {\it Ars Combin.,} {\bf 31} (1991), 239--248) in a stronger form when $m$ and $n$ are large. Building upon this exact result, we are able to determine the asymptotic value of $r(B_n^{(k)}, C_n)$ for each $k \geq 3$. Namely, we prove that for each $k \geq 3$, $r(B_n^{(k)}, C_n)= (k+1+o_k(1))n.$ This extends a result due to Rousseau and Sheehan (A class of Ramsey problems involving trees, {\it J.~London Math.~Soc.,} {\bf 18} (1978), 392--396)., Comment: Journal Ref. SIAM J. Discrete Math

We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular we show that in every cover of a Young diagram with $\binom{2k}{k}$ steps with generalized rectangles there is a row or a column in the diagram that is used by at least $k+1$ rectangles, and prove that this is best-possible. This answers two questions by Kim, Martin, Masa{\v{r}}{\'\i}k, Shull, Smith, Uzzell, and Wang (Europ. J. Comb. 2020), namely: - What is the local complete bipartite cover number of a difference graph? - Is there a sequence of graphs with constant local difference graph cover number and unbounded local complete bipartite cover number? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim \emph{et al.}, we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height~2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension $(1 + o(1))\log_2\log_2 n$. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension., Comment: Parts of this paper have previously been reported in arXiv submission arXiv:1902.08223

In this paper we describe a parallel algorithm for generating all non-isomorphic rank $3$ simple matroids with a given multiplicity vector. We apply our implementation in the HPC version of GAP to generate all rank $3$ simple matroids with at most $14$ atoms and a splitting characteristic polynomial. We have stored the resulting matroids alongside with various useful invariants in a publicly available, ArangoDB-powered database. As a byproduct we show that the smallest divisionally free rank $3$ arrangement which is not inductively free has $14$ hyperplanes and exists in all characteristics distinct from $2$ and $5$. Another database query proves that Terao's freeness conjecture is true for rank $3$ arrangements with $14$ hyperplanes in any characteristic., Improved exposition

The stable marriage problem is a matching problem that pairs members of two sets. The objective is to achieve a matching that satisfies all participants based on their preferences. The stable roommate problem is a variant involving only one set, which is partitioned into pairs with a similar objective. There exist asymptotically optimal algorithms that solve both problems.In this paper, the complexity of three-dimensional extensions of these problems is investigated. This is one of twelve research directions suggested by Knuth in his book on the stable marriage problem. It is shown that these problems are NP-complete, and hence it is unlikely that there exist efficient algorithms for their solutions.The approach developed in this paper provides an alternate NP-completeness proof for the hospitals/residents problem with couples—an important practical problem shown earlier to be NP-complete by Ronn.

A set of vertices D is a dominating set of a graph $G = ( V,E )$ if every vertex in $V - D$ is adjacent to a vertex in D. The domatic number $d ( G )$ of a graph $G = ( V,E )$ is the maximum number k such that V can be partitioned into k disjoint dominating sets $D_1 , \cdots ,D_k $. The main purpose of this paper is to give linear algorithms for the domatic number problem in interval graphs. This paper also proves that $d ( G ) = \delta ( G ) + 1$ for any interval graph G, where $\delta ( G )$ is the minimum degree of a vertex in G.

Many of the tools developed for the theory of tree-decompositions of graphs do not work for directed graphs. In this paper we show that some of the most basic tools do work in the case where the model digraph is a directed path. Using these tools we define a notion of a directed blockage in a digraph and prove a min-max theorem for directed path-width analogous to the result of Bienstock, Roberston, Seymour and Thomas for blockages in graphs. Furthermore, we show that every digraph with directed path width $\geq k$ contains each arboresence of order $\leq k + 1$ as a butterfly minor. Finally we also show that every digraph admits a linked directed path-decomposition of minimum width, extending a result of Kim and Seymour on semi-complete digraphs., 13 pages

The broadcast congested clique model (BClique) is a message-passing model of distributed computation where $n$ nodes communicate with each other in synchronous rounds. First, in this paper we prove...

The main theme of this paper is the enumeration of the occurrence of a pattern in words and permutations. We mainly focus on asymptotic properties of the sequence $f_r^v(k,n),$ the number of $n$-array $k$-ary words that contain a given pattern $v$ exactly $r$ times. In addition, we study the asymptotic behavior of the random variable $X_n,$ the number of pattern occurrences in a random $n$-array word. The two topics are closely related through the identity $P(X_n=r) = $ $\frac{1}{k^n}f_r^v(k,n).$ In particular, we show that for any $r\geq 0,$ the Stanley-Wilf sequence $\bigl(f_r^v(k,n)\bigr)^{1/n}$ converges to a limit independent of $r,$ and determine the value of the limit. We then obtain several limit theorems for the distribution of $X_n,$ including a CLT, large deviation estimates, and the exact growth rate of the entropy of $X_n.$ Furthermore, we introduce a concept of weak avoidance and link it to a certain family of non-product measures on words that penalize pattern occurrences but do not forbid them entirely. We analyze this family of probability measures in a small parameter regime, where the distributions can be understood as a perturbation of a uniform measure. Finally, we extend some of our results for words, including the one regarding the equivalence of the limits of the Stanley-Wilf sequences, to pattern occurrences in permutations., Comment: 33 pages

A rational link may be represented by any of the (infinitely) many link diagrams corresponding to various continued fraction expansions of the same rational number. The continued fraction expansion of the rational number in which all signs are the same is called a {\em nonalternating form} and the diagram corresponding to it is a reduced alternating link diagram, which is minimum in terms of the number of crossings in the diagram. Famous formulas exist in the literature for the braid index of a rational link by Murasugi and for its HOMFLY polynomial by Lickorish and Millet, but these rely on a special continued fraction expansion of the rational number in which all partial denominators are even (called {\em all-even form}). In this paper we present an algorithmic way to transform a continued fraction given in nonalternating form into the all-even form. Using this method we derive formulas for the braid index and the HOMFLY polynomial of a rational link in terms of its reduced alternating form, or equivalently the nonalternating form of the corresponding rational number.

Let $\Gamma$ be a graph with vertex set $V(\Gamma)$. A subset $C$ of $V(\Gamma)$ is called a perfect code in $\Gamma$ if $C$ is an independent set of $\Gamma$ and every vertex in $V(\Gamma)\setminus C$ is adjacent to exactly one vertex in $C$. A subset $C$ of a group $G$ is called a perfect code of $G$ if there exists a Cayley graph of $G$ which admits $C$ as a perfect code. A group $G$ is said to be code-perfect if every proper subgroup of $G$ is a perfect code of $G$. In this paper we prove that a group is code-perfect if and only if it has no elements of order $4$. We also prove that a proper subgroup $H$ of an abelian group $G$ is a perfect code of $G$ if and only if the Sylow $2$-subgroup of $H$ is a perfect code of the Sylow $2$-subgroup of $G$. This reduces the problem of determining when a given subgroup of an abelian group is a perfect code to the case of abelian $2$-groups. Finally, we determine all subgroup perfect codes in any generalized quaternion group., Comment: This is the final version to be published in SIAM Journal on Discrete Mathematics, 18 pp

In a recent paper, Garber, Gavrilyuk, and Magazinov [Discrete Comput. Geom., 53 (2015), pp. 245--260] proposed a sufficient combinatorial condition for a parallelohedron to be affinely Voronoi. We ...

The flip graph of triangulations has as vertices all triangulations of a convex $n$-gon, and an edge between any two triangulations that differ in exactly one edge. An $r$-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly $r$ times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of $r$-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex $n$-gon, the flip graph of plane trees on an arbitrary set of $n$ points, and the flip graph of non-crossing perfect matchings on a set of $n$ points in convex position. In addition, we consider two flip graphs on classes of non-geometric objects: the flip graph of permutations of $\{1,2,\dots,n\}$ and the flip graph of $k$-element subsets of $\{1,2,\dots,n\}$. In each of the five settings, we prove the existence and non-existence of rainbow cycles for different values of $r$, $n$ and~$k$.

In recent years, several classes of codes are introduced to provide some fault-tolerance and guarantee system reliability in distributed storage systems, among which locally repairable codes (LRCs for short) play an important role. However, most known constructions are over large fields with sizes close to the code length, which lead to the systems computationally expensive. Due to this, binary LRCs are of interest in practice. In this paper, we focus on binary linear LRCs with disjoint repair groups. We first derive an explicit bound for the dimension k of such codes, which can be served as a generalization of the bounds given in [11, 36, 37]. We also give several new constructions of binary LRCs with minimum distance $d = 6$ based on weakly independent sets and partial spreads, which are optimal with respect to our newly obtained bound. In particular, for locality $r\in \{2,3\}$ and minimum distance $d = 6$, we obtain the desired optimal binary linear LRCs with disjoint repair groups for almost all parameters.

Let $G$ be an $n$-vertex graph with $n\ge 3$. A classic result of Dirac from 1952 asserts that $G$ is hamiltonian if $\delta(G)\ge n/2$. Dirac's theorem is one of the most influential results in the study of hamiltonicity and by now there are many related known results\,(see, e.g., J. A. Bondy, Basic Graph Theory: Paths and Circuits, Chapter 1 in: {\it Handbook of Combinatorics Vol.1}). A {\it Halin graph} is a planar graph consisting of two edge-disjoint subgraphs: a spanning tree of at least 4 vertices and with no vertex of degree 2, and a cycle induced on the set of the leaves of the spanning tree. Halin graphs possess rich hamiltonicity properties such as being hamiltonian, hamiltonian connected, and almost pancyclic. As a continuous "generalization" of Dirac's theorem, in this paper, we show that there exists a positive integer $n_0$ such that any graph $G$ with $n\ge n_0$ vertices and $\delta(G)\ge (n+1)/2$ contains a spanning Halin subgraph. In particular, it contains a spanning Halin subgraph which is also pancyclic., Comment: 25 pages, 3 figures

The notion of digits in finite fields was introduced a few years ago as an attempt to deliver insight in related yet unresolved questions over the natural numbers. Several such intractable questions are related to the sum of digits function, which assigns to every natural number the sum of its digits. Its analogue over finite fields, which is a map from F_q to F_p, q = p h where p prime and h ≥ 2, has been studied by several authors. In particular, Cathy Swaenepoel [J. Number Theory, 189(2018), pp. 97-114] investigated the sum of digits of products of field elements. The main techniques involved were estimates on certain character sums and Gaussian sums over F_q and F_p. In this paper, we extend and generalize these results using a different approach, based on spectral graph theory, without any reference to character theory.

The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particular, this problem is one of the first problems studied in the framework of parameterized complexity. The nonuniform fixed-parameter tractability of Cycle Packing follows from the Robertson--Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time $2^{\mathcal{O}(k^2)}\cdot |V|$ using exponential space. In the case a solution exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a $2^{\mathcal{O}(k\log^2k)}\cdot |V|$-time (deterministic) algorithm using exponential space, which is a consequence of the Erdös--Pósa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time $2^{o(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, beating the bound $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, has been found. In light of this, it seems natural to ask whetherthe $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a $2^{\mathcal{O}(\frac{k\log^2k}{\log\log k})}\cdot |V|$-time (deterministic) algorithm for Cycle Packing. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, our algorithm runs in time linear in $|V|$, and its space complexity is polynomial in the input size. publishedVersion

The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection, and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is “judicious” in the sense that neither side is burdened by too many edges, and Balanced JB (BJB) also requires that the sizes of the sides themselves are “balanced” in the sense that neither of them is too large. Both of these problems were defined in the work by Bollobás and Scott and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is fixed parameter tractable (FPT) (which also proves that JB is FPT). publishedVersion

Gelfand-Tsetlin polytopes are prominent objects in algebraic combinatorics. The number of integer points of the Gelfand-Tsetlin polytope $\mathrm{GT}(\lambda)$ is equal to the dimension of the corresponding irreducible representation of $GL(n)$. It is well-known that the Gelfand-Tsetlin polytope is a marked order polytope; the authors have recently shown it to be a flow polytope. In this paper, we draw corollaries from this result and establish a general theory connecting marked order polytopes and flow polytopes., Comment: 18 pages, 10 figures

A Boolean function $g$ is said to be an optimal predictor for another Boolean function $f$ , if it minimizes the probability that $f(X^{n})\neq g(Y^{n})$ among all functions, where $X^{n}$ is uniform over the Hamming cube and $Y^{n}$ is obtained from $X^{n}$ by independently flipping each coordinate with probability $\delta$ . This paper is about self-predicting functions, which are those that coincide with their optimal predictor.

A fundamental graph problem is to recognize whether the vertex set of a graph $G$ can be bipartitioned into sets $A$ and $B$ such that $G[A]$ and $G[B]$ satisfy properties $\Pi_A$ and $\Pi_B$, respectively. This so-called $(\Pi_A,\Pi_B)$-Recognition problem generalizes amongst others the recognition of $3$-colorable, bipartite, split, and monopolar graphs. In this paper, we study whether certain fixed-parameter tractable $(\Pi_A,\Pi_B)$-Recognition problems admit polynomial kernels. In our study, we focus on the first level above triviality, where $\Pi_A$ is the set of $P_3$-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph $G[A]$, and $\Pi_B$ is characterized by a set $\mathcal{H}$ of connected forbidden induced subgraphs. We prove that, under the assumption that NP is not a subset of coNP/poly, \textsc{$(\Pi_A,\Pi_B)$-Recognition} admits a polynomial kernel if and only if $\mathcal{H}$ contains a graph with at most $2$ vertices. In both the kernelization and the lower bound results, we exploit the properties of a pushing process, which is an algorithmic technique used recently by Heggerness et al. and by Kanj et al. to obtain fixed-parameter algorithms for many cases of $(\Pi_A,\Pi_B)$-Recognition, as well as several other problems., Comment: Full version of the corresponding article in the Proceedings of the 26th Annual European Symposium on Algorithms (ESA '18), 35 pages, 7 figures

The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size. Using a new Erdos-Posa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of ChVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, ``Chordal Deletion Is Fixed-Parameter Tractable,"" in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37--48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for ChVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size \scrO (k4 log2 k).

Conflict-free coloring of hypergraphs is a very well studied question of theoretical and practical interest. For a hypergraph H = (U, F), a conflict-free coloring of H refers to a vertex coloring where every hyperedge has a vertex with a unique color, distinct from all other vertices in the hyperedge. In this paper, we initiate a study of a natural maximization version of this problem, namely, Max-CFC: For a given hypergraph H and a fixed r ≥ 2, color the vertices of U using r colors so that the number of hyperedges that are conflict-free colored is maximized. By previously known hardness results for conflict-free coloring, this maximization version is NP-hard. We study this problem in the context of both exact and parameterized algorithms. In the parameterized setting, we study this problem with respect to a natural parameter—the solution size. In particular, the question we study is the following: p-CFC: For a given hypergraph, can we conflict-free color at least k hyperedges with at most r colors, the parameter being the solution size k. We show that this problem is fixed parameter tractable by designing an algorithm with running time 2O(k log log k+k log r)(n + m)O (1) using a novel connection to the Unique Coverage problem and applying the method of color coding in a nontrivial manner. For the special case for hypergraphs induced by graph neighborhoods we give a polynomial kernel. Finally, we give an exact algorithm for Max-CFC running in O(2n+m) time. All our algorithms, with minor modifications, work for a stronger version of conflict-free coloring, Unique Maximum Coloring.

A graphic sequence $\pi$ is potentially $H$-graphic if there is some realization of $\pi$ that contains $H$ as a subgraph. The Erd\H{o}s-Jacobson-Lehel problem asks to determine $\sigma(H,n)$, the minimum even integer such that any $n$-term graphic sequence $\pi$ with sum at least $\sigma(H,n)$ is potentially $H$-graphic. The parameter $\sigma(H,n)$ is known as the potential function of $H$, and can be viewed as a degree sequence variant of the classical extremal function ${\rm ex}(n,H)$. Recently, Ferrara, LeSaulnier, Moffatt and Wenger [On the sum necessary to ensure that a degree sequence is potentially $H$-graphic, Combinatorica 36 (2016), 687--702] determined $\sigma(H,n)$ asymptotically for all $H$, which is analogous to the Erd\H{o}s-Stone-Simonovits Theorem that determines ${\rm ex}(n,H)$ asymptotically for nonbipartite $H$. In this paper, we investigate a stability concept for the potential number, inspired by Simonovits' classical result on the stability of the extremal function. We first define a notion of stability for the potential number that is a natural analogue to the stability given by Simonovits. However, under this definition, many families of graphs are not $\sigma$-stable, establishing a stark contrast between the extremal and potential functions. We then give a sufficient condition for a graph $H$ to be stable with respect to the potential function, and characterize the stability of those graphs $H$ that contain an induced subgraph of order $\alpha(H)+1$ with exactly one edge., Comment: 20 pages, 3 figures

The Brunn--Minkowski inequality states that the volume of compact sets $K,L\subset\mathbb{R}^n$ satisfies $\mathrm{vol}(K+L)^{1/n}\geq\mathrm{vol}(K)^{1/n}+\mathrm{vol}(L)^{1/n}$. In this paper we ...

A family $\mathcal A$ of subsets of an $n$-element set is called an eventown (resp., oddtown) if all its sets have even (resp., odd) size and all pairwise intersections have even size. Using tools from linear algebra, it was shown by Berlekamp and Graver that the maximum size of an eventown is $2^{\left\lfloor n/2\right\rfloor}$. On the other hand (somewhat surprisingly), it was proven by Berlekamp that oddtowns have size at most $n$. Over the last four decades, many extensions of this even/oddtown problem have been studied. In this paper we present new results on two such extensions. First, extending a result of Vu, we show that a $k$-wise eventown (i.e., intersections of $k$ sets are even) has for $k \geq 3$ a unique extremal configuration and obtain a stability result for this problem. Next we improve some known bounds for the defect version of an $\ell$-oddtown problem. In this problem we consider sets of size $\not\equiv 0 \pmod \ell$ where $\ell$ is a prime number (not necessarily 2) and allow a few...

International audience; Let $k,d,\lambda \geqslant 1$ be integers with $d\geqslant \lambda $ and let $X$ be a finite set of points in $\mathbb{R}^{d}$. A $(d-\lambda)$-plane $L$ transversal to the convex hulls of all $k$-sets of $X$ is called Kneser transversal. If in addition $L$ contains $(d-\lambda)+1$ points of $X$, then $L$ is called complete Kneser transversal.In this paper, we present various results on the existence of (complete) Kneser transversals for $\lambda =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-\lambda)$ points in $\mathbb{R}^d$ with $k-\lambda\geqslant 2$ and $\lambda =2,3$. We then present a description of Kneser transversals $L$ of collections of $d+2(k-\lambda)$ points in $\mathbb{R}^d$ with $k-\lambda\geqslant 2$ for $\lambda =2,3$. We show that either $L$ is a complete Kneser transversal or it contains $d-2(\lambda-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 $\lambda =2$ and $3$) for $m(k,d,\lambda)$ defined as the maximum positive integer $n$ such that every set of $n$ points (not necessarily in general position) in $\mathbb{R}^{d}$ 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 $\mathbb{R}^3$.

In this paper we determine the chromatic number of graphs with two odd cycle lengths. Let $G$ be a graph and $L(G)$ be the set of all odd cycle lengths of $G$. We prove that: (1) If $L(G)=\{3,3+2l\}$, where $l\geq 2$, then $\chi(G)=\max\{3,\omega(G)\}$; (2) If $L(G)=\{k,k+2l\}$, where $k\geq 5$ and $l\geq 1$, then $\chi(G)=3$. These, together with the case $L(G)=\{3,5\}$ solved in \cite{W}, give a complete solution to the general problem addressed in \cite{W,CS,KRS}. Our results also improve a classical theorem of Gy\'{a}rf\'{a}s which asserts that $\chi(G)\le 2|L(G)|+2$ for any graph $G$., Comment: 26 pages,accepted version for publication in SIAM J. Discrete Math

Gy\'arf\'as, Gy\H{o}ri and Simonovits proved that if a $3$-uniform hypergraph with $n$ vertices has no linear cycles, then its independence number $\alpha \ge \frac{2n} {5}$. The hypergraph consisting of vertex disjoint copies of a complete hypergraph $K_5^3$ on five vertices, shows that equality can hold. They asked whether this bound can be improved if we exclude $K_5^3$ as a subhypergraph and whether such a hypergraph is $2$-colorable. In this paper we answer these questions affirmatively. Namely, we prove that if a $3$-uniform linear-cycle-free hypergraph doesn't contain $K_5^3$ as a subhypergraph, then it is $2$-colorable. This result clearly implies that its independence number $\alpha \ge \lceil \frac{n}{2} \rceil$. We show that this bound is sharp. Gy\'arf\'as, Gy\H{o}ri and Simonovits also proved that a linear-cycle-free $3$-uniform hypergraph contains a vertex of strong degree at most 2. In this context, we show that a linear-cycle-free $3$-uniform hypergraph has a vertex of degree at most $n-2$ when $n \ge 10$., Comment: Improved the writing, more explanation added and corrections made

Hajos conjectured in 1961 that every $k$-chromatic graph contains a $K_k$-subdivision. In this paper, we consider the subdivision of $K_5^-$ and prove that every 4-connected graph contains a $K_5^-...

In the Vertex Cover problem we are given a graph $G=(V,E)$ and an integer $k$ and have to determine whether there is a set $X\subseteq V$ of size at most $k$ such that each edge in $E$ has at least one endpoint in $X$. The problem can be easily solved in time $O^*(2^k)$, making it fixed-parameter tractable (FPT) with respect to $k$. While the fastest known algorithm takes only time $O^*(1.2738^k)$, much stronger improvements have been obtained by studying parameters that are smaller than $k$. Apart from treewidth-related results, the arguably best algorithm for Vertex Cover runs in time $O^*(2.3146^p)$, where $p=k-LP(G)$ is only the excess of the solution size $k$ over the best fractional vertex cover (Lokshtanov et al.\ TALG 2014). Since $p\leq k$ but $k$ cannot be bounded in terms of $p$ alone, this strictly increases the range of tractable instances. Recently, Garg and Philip (SODA 2016) greatly contributed to understanding the parameterized complexity of the Vertex Cover problem. They prove that $2LP(G)-MM(G)$ is a lower bound for the vertex cover size of $G$, where $MM(G)$ is the size of a largest matching of $G$, and proceed to study parameter $\ell=k-(2LP(G)-MM(G))$. They give an algorithm of running time $O^*(3^\ell)$, proving that Vertex Cover is FPT in $\ell$. It can be easily observed that $\ell\leq p$ whereas $p$ cannot be bounded in terms of $\ell$ alone. We complement the work of Garg and Philip by proving that Vertex Cover admits a randomized polynomial kernelization in terms of $\ell$, i.e., an efficient preprocessing to size polynomial in $\ell$. This improves over parameter $p=k-LP(G)$ for which this was previously known (Kratsch and Wahlstr\"om FOCS 2012)., Comment: Full version of ESA 2016 paper

We study the problem of routing symmetric demand pairs in planar digraphs. The input consists of a directed planar graph G = (V, E) and a collection of k source-destination pairs M = {s_1t_1, ..., s_kt_k}. The goal is to maximize the number of pairs that are routed along disjoint paths. A pair s_it_i is routed in the symmetric setting if there is a directed path connecting s_i to t_i and a directed path connecting t_i to s_i. In this paper we obtain a randomized poly-logarithmic approximation with constant congestion for this problem in planar digraphs. The main technical contribution is to show that a planar digraph with directed treewidth h contains a constant congestion crossbar of size Omega(h/polylog(h)).

For nonnegative integers $k, d_1, \ldots, d_k$, a graph is $(d_1, \ldots, d_k)$-colorable if its vertex set can be partitioned into $k$ parts so that the $i$th part induces a graph with maximum degree at most $d_i$ for all $i\in\{1, \ldots, k\}$. A class $\mathcal C$ of graphs is balanced $k$-partitionable and unbalanced $k$-partitionable if there exists a nonnegative integer $D$ such that all graphs in $\mathcal C$ are $(D, \ldots, D)$-colorable and $(0, \ldots, 0, D)$-colorable, respectively, where the tuple has length $k$. A set $X$ of cycles is a cycle obstruction set of a class $\mathcal C$ of planar graphs if every planar graph containing none of the cycles in $X$ as a subgraph belongs to $\mathcal C$. This paper characterizes all cycle obstruction sets of planar graphs to be balanced $k$-partitionable and unbalanced $k$-partitionable for all $k$; namely, we identify all inclusionwise minimal cycle obstruction sets for all $k$.

A permutation rational function $f\in \mathbb{F}_q(x)$ is a rational function that induces a bijection on $\mathbb{F}_q$, that is, for all $y\in\mathbb{F}_q$ there exists exactly one $x\in\mathbb{F}_q$ such that $f(x)=y$. Permutation rational functions are intimately related to exceptional rational functions, and more generally exceptional covers of the projective line, of which they form the first important example. In this paper, we show how to efficiently generate many permutation rational functions over large finite fields using isogenies of elliptic curves, and discuss some cryptographic applications. Our algorithm is based on Fried's modular interpretation of certain dihedral exceptional covers of the projective line (Cont. Math., 1994).

The rigidity of a matrix A for a target rank r over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in Computational Complexity Theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of Parameterized Complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of Parameterized Complexity. Naturally, given parameters r and k, the Matrix Rigidity problem asks whether the rigidity of A for the target rank r is at most k. We show that in case F equals the reals or F is any finite field, this problem is fixed-parameter tractable with respect to k+r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in Real Algebraic Geometry, which are not well known in Parameterized Complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.

In this paper, we study 3-colorable graphs having no induced 8-vertex path and no induced cycles of specific lengths. We prove a characterization by critical graphs in three particular cases.

The Densest $k$-Subgraph (D$k$S) problem, and its corresponding minimization problem Smallest $p$-Edge Subgraph (S$p$ES), have come to play a central role in approximation algorithms. This is due both to their practical importance, and their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not an admit a subpolynomial approximation ratio (although the best known hardness results do not rule this out). In this paper we generalize both D$k$S and S$p$ES from graphs to hypergraphs. We consider the Densest $k$-Subhypergraph problem (given a hypergraph $(V, E)$, find a subset $W\subseteq V$ of $k$ vertices so as to maximize the number of hyperedges contained in $W$) and define the Minimum $p$-Union problem (given a hypergraph, choose $p$ of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest non-graph setting. For this case we provide an $O(n^{4(4-\sqrt{3})/13 + \epsilon}) \leq O(n^{0.697831+\epsilon})$-approximation (for arbitrary constant $\epsilon > 0$) for Densest $k$-Subhypergraph and an $\tilde O(n^{2/5})$-approximation for Minimum $p$-Union. We also give an $O(\sqrt{m})$-approximation for Minimum $p$-Union in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial time solution on these instances., Comment: 21 pages

2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some 2-level polytopes arising in combinatorial settings. Our first contribution is proving that f(0)(P)f(d-1) (P)

A (simple) $k$-matching in a graph is a subgraph all of whose nodes have degree at most $k$. The $k$-matching problem is to find a $k$-matching with a maximum number of edges. Well-known results for the classical $1$-matching problem, such as the Tutte--Berge min-max theorem and Edmonds's polynomial-time algorithm, are known to generalize to $k$-matchings. These 1-matching results are also known to generalize to the problem of finding a subgraph, with a maximum number of nodes, whose connected components are isolated edges and 1-critical (or hypomatchable) graphs from a specified set (e.g., triangles or pentagons). In this paper we present a new common generalization of these two generalized 1-matching problems. We present an algorithm, a min-max theorem, and a structure theorem (that generalizes the Edmonds--Gallai theorem for 1-matchings). Even when specialized to $k$-matchings, our min-max and structure theorems appear to be new.

In this paper, we are concerned with counting corners of core partitions. We introduce the concepts of stitches and antistitches, which are pairs of cells in a quotient space which we call wrap-up space. We prove that the antistitches of a rational Dyck path are in bijection with the segments of structure sets of the corresponding core partition; therefore the corners of a core partition can be counted by the number of stitches or antistitches. Based on these results, for coprime positive integers $a$ and $b$, we give two essentially different formulae for the number of corners in all $(a,b)$-cores. This leads to an unexpected identity, expressing the rational Catalan numbers as weighed sums of binomial numbers. Moreover, we show that for an $(n,n+1)$-core partition $\lambda$ determined by a certain $(n,n+1)$-Dyck path $P$, the corners of $\lambda$ correspond to pairs of consecutive right steps in $P$. As a consequence, we show that the number of $(n,n+1)$-cores with $k$ corners is the Narayana number $N(...