Combinatorial Algorithms

Frontmatter

Speeding Up Cover Time of Sparse Graphs Using Local Knowledge

Abstract

We analyse the cover time of a random walk on a random graph of a given degree sequence. Weights are assigned to the edges of the graph using a certain type of scheme that uses only local degree knowledge. This biases the transitions of the walk towards lower degree vertices. We demonstrate that, with high probability, the cover time is at most \((1+o(1))\frac{d-1}{d-2}8n\log n\), where d is the minimum degree. This is in contrast to the precise cover time of \((1+o(1))\frac{d-1}{d-2}\frac{\theta }{d} n\log n\) (with high probability) given in [1] for a simple (i.e., unbiased) random walk on the same graph model. Here \(\theta \) is the average degree and since the ratio \(\theta /d\) can be arbitrarily large, or go to infinity with n, we see that the scheme can give an unbounded speed up for sparse graphs.

Mohammed Amin Abdullah, Colin Cooper, Moez Draief

Minimum Activation Cost Edge-Disjoint Paths in Graphs with Bounded Tree-Width

Abstract

In activation network problems we are given a directed or undirected graph \(G=(V,E)\) with a family \(\{f_{uv} : (u,v)\in E\}\) of monotone non-decreasing activation functions from \(D^2\) to \(\{0,1\}\), where D is a constant-size subset of the non-negative real numbers, and the goal is to find activation values \(x_v \in D\) for all \(v\in V\) of minimum total cost \(\sum _{v \in V}{x_v}\) such that the activated set of edges satisfies some connectivity requirements. We propose an algorithm that optimally solves the minimum activation cost of k edge-disjoint st -paths (st-MAEDP) problem in \(O(|V||D|^{tw+1}tw^3(k+1)^{(tw +3)^{2(tw +3)}}(tw+3)^{2(tw+3)+3})\) time for graphs with treewidth bounded by a constant tw.

Hasna Mohsen Alqahtani, Thomas Erlebach

A Fast Scaling Algorithm for the Weighted Triangle-Free 2-Matching Problem

Abstract

A perfect 2-matching in an undirected graph \(G = (V, E)\) is a function \(x :E \rightarrow \left\{ 0,1,2 \right\} \) such that for each node \(v \in V\) the sum of values x(e) on all edges e incident to v equals 2. If \(\mathop {\text {supp}}\nolimits (x) = \left\{ e \in E \mid x(e) \ne 0 \right\} \) contains no triangles, then x is called triangle-free. Polyhedrally, triangle-free 2-matchings are harder than 2-matchings, but easier than usual 1-matchings.

Concerning the weighted case, Cornuéjols and Pulleyblank devised a combinatorial strongly-polynomial algorithm that finds a perfect triangle-free 2-matching of minimum cost. A suitable implementation of their algorithm runs in \(O(VE \log V)\) time.

In case of integer edge costs in the range [0, C], for both 1- and 2-matchings some faster scaling algorithms are known that find optimal solutions within \(O(\sqrt{V\alpha (E, V)\log {V}}E \log (VC))\) and \(O(\sqrt{V}E \log (VC))\) time, respectively, where \(\alpha \) denotes the inverse Ackermann function. So far, no efficient cost-scaling algorithm is known for finding a minimum-cost perfect triangle-free 2-matching. The present paper fills this gap by presenting such an algorithm with time complexity of \(O(\sqrt{V}E \log {V} \log (VC))\).

Stepan Artamonov, Maxim Babenko

1-Page and 2-Page Drawings with Bounded Number of Crossings per Edge

Abstract

A 2-page drawing of a graph is such that the vertices are drawn as points along a line and each edge is a circular arc in one of the two half-planes defined by this line. If all edges are in the same half-plane, the drawing is called a 1-page drawing. We want to compute 1-page and 2-page drawings of planar graphs such that the number of crossings per edge does not depend on the number of the vertices. We show that for any constant k, there exist planar graphs that require more than k crossings per edge in either a 1-page or a 2-page drawing. We then prove that if the vertex degree is bounded by \(\varDelta \), every planar 3-tree has a 2-page drawing with a number of crossings per edge that only depends on \(\varDelta \). Finally, we show a similar result for 1-page drawings of partial 2-trees.

Carla Binucci, Emilio Di Giacomo, Md. Iqbal Hossain, Giuseppe Liotta

Longest Common Extensions in Partial Words

Abstract

The Longest Common Extension of a pair of positions (i, j) in a string, or word, is the longest substring starting at i and j. The LCE problem considers a word and a set of pairs of positions and computes for each pair in the set, the longest common extension starting at both positions in the pair. This problem finds applications in matching with don’t-care characters, approximate string searching, finding all exact or approximate tandem repeats, to name a few. From a practical point of view, Ilie et al. (Journal of Discrete Algorithms, 2010) looked for simple and efficient algorithms for the LCE problem. In this paper, we extend their analyses to partial words, strings with don’t-cares or holes. In this context, we compute the Longest Common Compatible Extension of each pair of positions (i, j) in a partial word, i.e., the longest substrings starting at i and j that are compatible. We show that our results match with those of total words (partial words without holes). We find that one of the simplest algorithms for implementing the LCE problem is optimal on average in this case.

Francine Blanchet-Sadri, Rachel Harred, Justin Lazarow

Adding Isolated Vertices Makes Some Online Algorithms Optimal

Abstract

An unexpected difference between online and offline algorithms is observed. The natural greedy algorithms are shown to be worst case online optimal for Online Independent Set and Online Vertex Cover on graphs with “enough” isolated vertices, Freckle Graphs. For Online Dominating Set, the greedy algorithm is shown to be worst case online optimal on graphs with at least one isolated vertex. These algorithms are not online optimal in general. The online optimality results for these greedy algorithms imply optimality according to various worst case performance measures, such as the competitive ratio. It is also shown that, despite this worst case optimality, there are Freckle graphs where the greedy independent set algorithm is objectively less good than another algorithm.

It is shown that it is NP-hard to determine any of the following for a given graph: the online independence number, the online vertex cover number, and the online domination number.

Joan Boyar, Christian Kudahl

Gray Codes for AT-Free Orders via Antimatroids

Abstract

The \({{\mathrm{\mathrm {AT}}}}\)-free order is a linear order of the vertices of a graph the existence of which characterizes \({{\mathrm{\mathrm {AT}}}}\)-free graphs. We show that all \({{\mathrm{\mathrm {AT}}}}\)-free orders of an \({{\mathrm{\mathrm {AT}}}}\)-free graph can be generated in O(1) amortized time.

Jou-Ming Chang, Ton Kloks, Hung-Lung Wang

Enumerating Cyclic Orientations of a Graph

Abstract

Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge so as to obtain a directed acyclic graph (DAG) with the same vertex set; it is cyclic otherwise. As far as we know, only the enumeration of acyclic orientations has been addressed in the literature. In this paper, we pose the problem of efficiently enumerating all the cyclic orientations of an undirected connected graph with n vertices and m edges, observing that it cannot be solved using algorithmic techniques previously employed for enumerating acyclic orientations. We show that the problem is of independent interest from both combinatorial and algorithmic points of view, and that each cyclic orientation can be listed with \(\tilde{O}(m)\) delay time. Space usage is O(m) with an additional setup cost of \(O(n^2)\) time before the enumeration begins, or O(mn) with a setup cost of \(\tilde{O}(m)\) time.

Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi

Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

Abstract

We consider a natural restriction of the List Colouring problem, k-Regular List Colouring, which corresponds to the List Colouring problem where every list has size exactly k. We give a complete classification of the complexity of k-Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs and to planar graphs with no 4-cycles and no 5-cycles. We also give a complete classification of the complexity of this problem and a number of related colouring problems for graphs with bounded maximum degree.

Konrad K. Dabrowski, François Dross, Matthew Johnson, Daniël Paulusma

Combinatorial Properties of Full-Flag Johnson Graphs

Abstract

The Johnson graphs J(n, k) are a well-known family of combinatorial graphs whose applications and generalizations have been studied extensively in the literature. In this paper, we present a new variant of the family of Johnson graphs, the Full-Flag Johnson graphs, and discuss their combinatorial properties. We show that the Full-Flag Johnson graphs are Cayley graphs on \(S_n\) generated by certain well-known classes of permutations and that they are in fact generalizations of permutahedra. Our main result will be to establish a tight \(\varTheta (n^2/k^2)\) bound for the diameter of the Full-Flag Johnson graph FJ(n, k).

Irving Dai

List Colouring and Partial List Colouring of Graphs On-line

Abstract

In this paper, we investigate the problem of graph list colouring in the on-line setting. We provide several results on paintability of graphs in the model introduced by Schauz [18] and Zhu [25]. We prove that the on-line version of Ohba’s conjecture is true for the class of planar graphs. We show that the conjecture for partial list colouring on-line holds for several graph classes, namely claw-free graphs, maximal planar graphs, series-parallel graphs, and chordal graphs.

Martin Derka, Alejandro López-Ortiz, Daniela Maftuleac

About Ungatherability of Oblivious and Asynchronous Robots on Anonymous Rings

Abstract

We investigate on gathering of identical, memoryless, and mobile robots placed on the nodes of anonymous graphs. According to the well-known Look-Compute-Move model, robots operate in asynchronous cycles. In one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move (Move). Cycles are performed asynchronously for each robot. The gathering problem asks for a strategy that brings all robots to a common node.

Several papers have been investigating the problem for various settings on ring graphs due its combinatorial relevance. However, none of the provided solutions can cope with the case of four robots, the only case still open on ring graphs, even though it is conjectured that the gathering is possible. We consider the specific cases of four robots placed on a ring of seven and nine nodes. We present an exhaustive proof about the impossibility of designing a strategy that solves the gathering in the considered setting. The proof makes use of both theoretical and computer-assisted approaches. Despite the specific cases considered, the relevance of the provided proof is twofold. On the one hand, it disproves the conjecture posed by previous works. On the other hand, it provides a new approach and new insights to the gathering problem on rings.

Gabriele Di Stefano, Pietro Montanari, Alfredo Navarra

Dynamic Subtrees Queries Revisited: The Depth First Tour Tree

Abstract

In the dynamic tree problem the goal is the maintenance of an arbitrary n-vertex forest, where the trees are subject to joining and splitting by, respectively, adding and removing edges. Depending on the application, information can be associated to nodes or edges (or both), and queries might require to combine values in path or (sub)trees. In this paper we present a novel data structure, called the Depth First Tour Tree, based on a linearization of a DFS visit of the tree. Despite the simplicity of the approach, similar to the ET-Trees (based on a Euler Tour), our data structure is able to answer queries related to both paths and (sub)trees. In particular, focusing on subtree computations, we show how to customize the data structure in order to answer queries for a concrete application: keeping track of the biconnectivity measures, including the impact of the removal of articulation points, of a dynamic undirected graph.

Gabriele Farina, Luigi Laura

Schröder Partitions and Schröder Tableaux

Abstract

We introduce the notions of Schröder shape and of Schröder tableau, which provide some kind of analogs of the classical notions of Young shape and Young tableau. We investigate some properties of the partial order given by containment of Schröder shapes. Then we propose an algorithm which is the natural analog of the well known RS correspondence for Young tableaux, and we characterize those permutations whose insertion tableaux have some special shapes. We end our paper with a few suggestions for possible further work.

Luca Ferrari

Algorithmic Aspects of the S-Labeling Problem

Abstract

Given a graph \(G = (V,E)\) of order n and maximum degree \(\varDelta \), the NP-complete S-labeling problem consists in finding a labeling of G, i.e. a bijective mapping \(\phi : V \rightarrow \{1, 2 \ldots n\}\), such that \(\mathrm{SL}_{\phi }(G)=\sum _{\{u,v\} \in E} \min \{\phi (u), \phi (v)\}\) is minimized. A preliminary study of the S-labeling problem has been undertaken in [9]; here, we prolongate this study, and focus more specifically on algorithmic results concerning the problem. We first give intrinsic properties of optimal labelings, which will prove useful for our algorithmic study. We then show that the S-Labeling problem is polynomial-time solvable for (sets of) caterpillars. We also provide upper and lower bounds on \(\mathrm{SL}_{\phi }(G)\), that in turn allow us to determine polynomial-time approximation algorithms for different classes of graphs such as regular graphs, connected graphs and forests, but also for general graphs. Concerning exact algorithms, we show that the problem is solvable in \(O^*(1.44225^{n\varDelta })\) time, and that deciding whether there exist a labeling \(\phi \) of G such that \(\mathrm{SL}_{\phi }(G) \le |E| + k\) is solvable in \(O^*(2^{2\sqrt{k}}\ (2 \sqrt{k})!)\).

Guillaume Fertin, Irena Rusu, Stéphane Vialette

Contagious Sets in Dense Graphs

Abstract

We study the activation process in undirected graphs known as bootstrap percolation: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it had at least r active neighbors, for a threshold r that is identical for all vertices. A contagious set is a vertex set whose activation results with the entire graph being active. Let m(G, r) be the size of a smallest contagious set in a graph G. We examine density conditions that ensure that a given n-vertex graph \(G=(V,E)\) has a small contagious set. With respect to the minimum degree, we prove that if G has minimum degree \(n{\slash }2\) then \(m(G,2)=2\). We also provide tight upper bounds on the number of rounds until all nodes are active.

For \(n \ge k \ge r\), we denote by M(n, k, r) the maximum number of edges in an n-vertex graph G satisfying \(m(G,r)>k\). We determine the precise value of M(n, k, 2) and M(n, k, k) assuming that n is sufficiently large compared to k.

Daniel Freund, Matthias Poloczek, Daniel Reichman

Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time

Abstract

A phylogenetic network is a rooted acyclic digraph whose leaves are labeled with a set of taxa. The tree containment problem is a fundamental problem arising from model validation in the study of phylogenetic networks. It asks to determine whether or not a given network displays a given phylogenetic tree over the same leaf set. It is known to be NP-complete in general. Whether or not it remains NP-complete for stable networks is an open problem. We make progress towards answering that question by presenting a quadratic time algorithm to solve the tree containment problem for a new class of networks that we call genetically stable networks, which include tree-child networks and comprise a subclass of stable networks.

Philippe Gambette, Andreas D. M. Gunawan, Anthony Labarre, Stéphane Vialette, Louxin Zhang

On the Complexity of Rainbow Coloring Problems

Abstract

An edge-colored graph G is said to be rainbow connected if between each pair of vertices there exists a path which uses each color at most once. The rainbow connection number, denoted by \({{\mathrm{rc}}}(G)\), is the minimum number of colors needed to make G rainbow connected. Along with its variants, which consider vertex colorings and/or so-called strong colorings, the rainbow connection number has been studied from both the algorithmic and graph-theoretic points of view.

In this paper we present a range of new results on the computational complexity of computing the four major variants of the rainbow connection number. In particular, we prove that the Strong Rainbow Vertex Coloring problem is \(\textsf {NP}\)-complete even on graphs of diameter 3. We show that when the number of colors is fixed, then all of the considered problems can be solved in linear time on graphs of bounded treewidth. Moreover, we provide a linear-time algorithm which decides whether it is possible to obtain a rainbow coloring by saving a fixed number of colors from a trivial upper bound. Finally, we give a linear-time algorithm for computing the exact rainbow connection numbers for three variants of the problem on graphs of bounded vertex cover number.

Eduard Eiben, Robert Ganian, Juho Lauri

How to Design Graphs with Low Forwarding Index and Limited Number of Edges

Abstract

The (edge) forwarding index of a graph is the minimum, over all possible routings of all the demands, of the maximum load of an edge. This metric is of a great interest since it captures the notion of global congestion in a precise way: the lesser the forwarding-index, the lesser the congestion. In this paper, we study the following design question: Given a number e of edges and a number n of vertices, what is the least congested graph that we can construct? and what forwarding-index can we achieve? Our problem has some distant similarities with the well-known \((\varDelta ,D)\) problem, and we sometimes build upon results obtained on it. The goal of this paper is to study how to build graphs with low forwarding indices and to understand how the number of edges impacts the forwarding index. We answer here these questions for different families of graphs: general graphs, graphs with bounded degree, sparse graphs with a small number of edges by providing constructions, most of them asymptotically optimal. For instance, we provide an asymptotically optimal construction for \((n,n+k)\) cubic graphs - its forwarding index is \(\sim \frac{n^2}{3k} \log _2(k)\). Our results allow to understand how the forwarding-index drops when edges are added to a graph and also to determine what is the best (i.e. least congested) structure with e edges. Doing so, we partially answer the practical problem that initially motivated our work: If an operator wants to power only e links of its network, in order to reduce the energy consumption (or wiring cost) of its networks, what should be those links and what performance can be expected?

Frédéric Giroire, Stéphane Pérennes, Issam Tahiri

Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs

Abstract

Connected Vertex Cover is one of the classical problems of computer science, already mentioned in the monograph of Garey and Johnson [15]. Although the optimization and decision variants of finding connected vertex covers of minimum size or weight are well studied, surprisingly there is no work on the enumeration or maximum number of minimal connected vertex covers of a graph. In this paper we show that the maximum number of minimal connected vertex covers of a graph is \(O(1.8668^n)\), and these can be enumerated in time \(O(1.8668^n)\). For graphs of chordality at most 5, we are able to give a better upper bound, and for chordal graphs and distance-hereditary graphs we are able to give tight bounds on the maximum number of minimal connected vertex covers.

Petr A. Golovach, Pinar Heggernes, Dieter Kratsch

Fast Multiple Order-Preserving Matching Algorithms

Abstract

Given a text T and a pattern P, the order-preserving matching problem is to find all substrings in T which have the same relative orders as P. Order-preserving matching has been an active research area since it was introduced by Kubica et al. [13] and Kim et al. [11]. In this paper we present two algorithms for the multiple order-preserving matching problem, one of which runs in sublinear time on average and the other in linear time on average. Both algorithms run much faster than the previous algorithms.

Myoungji Han, Munseong Kang, Sukhyeun Cho, Geonmo Gu, Jeong Seop Sim, Kunsoo Park

Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees

Abstract

Completely independent spanning trees \(T_1,T_2,\ldots ,T_k\) in a graph G are spanning trees in G such that for any pair of distinct vertices u and v, the k paths in the spanning trees between u and v mutually have no common edge and no common vertex except for u and v. The concept finds applications in fault-tolerant communication problems in a network. Recently, it was shown that Dirac’s condition for a graph to be hamiltonian is also a sufficient condition for a graph to have two completely independent spanning trees. In this paper, we generalize this result to three or more completely independent spanning trees. Namely, we show that for any graph G with \(n \ge 7\) vertices, if the minimum degree of a vertex in G is at least \(n-k\), where \(3 \le k \le \frac{n}{2}\), then there are \(\lfloor \frac{n}{k} \rfloor \) completely independent spanning trees in G. Besides, we improve the lower bound of \(\frac{n}{2}\) on the Dirac’s condition for completely independent spanning trees to \(\frac{n-1}{2}\) except for some specific graph. Our results are theoretical ones, since these minimum degree conditions can be applied only to a very dense graph. We then present constructions of symmetric regular graphs which include optimal graphs with respect to the number of completely independent spanning trees.

Toru Hasunuma

A Faster FPTAS for the Unbounded Knapsack Problem

Abstract

The Unbounded Knapsack Problem (UKP) is a well-known variant of the famous 0-1 Knapsack Problem (0-1 KP). In contrast to 0-1 KP, an arbitrary number of copies of every item can be taken in UKP. Since UKP is NP-hard, fully polynomial time approximation schemes (FPTAS) are of great interest. Such algorithms find a solution arbitrarily close to the optimum \(\mathrm {OPT}(I)\), i.e. of value at least \((1-\varepsilon ) \mathrm {OPT}(I)\) for \(\varepsilon > 0\), and have a running time polynomial in the input length and \(\frac{1}{\varepsilon }\). For over thirty years, the best FPTAS was due to Lawler with a running time in \(O(n + \frac{1}{\varepsilon ^3})\) and a space complexity in \(O(n + \frac{1}{\varepsilon ^2})\), where n is the number of knapsack items. We present an improved FPTAS with a running time in \(O(n + \frac{1}{\varepsilon ^2} \log ^3 \frac{1}{\varepsilon })\) and a space bound in \(O(n + \frac{1}{\varepsilon } \log ^2 \frac{1}{\varepsilon })\). This directly improves the running time of the fastest known approximation schemes for Bin Packing and Strip Packing, which have to approximately solve UKP instances as subproblems.

Klaus Jansen, Stefan E. J. Kraft

Computational Complexity of Distance Edge Labeling

Abstract

The problem of Distance Edge Labeling is a variant of Distance Vertex Labeling (also known as \(\mathrm{L}_{2,1}\) labeling) that has been studied for more than twenty years and has many applications, such as frequency assignment.

The Distance Edge Labeling problem asks whether the edges of a given graph can be labeled such that the labels of adjacent edges differ by at least two and the labels of edges at distance two differ by at least one. Labels are chosen from the set \(\{0,1,\dots ,\lambda \}\) for \(\lambda \) fixed.

We present a full classification of its computational complexity—a dichotomy between the polynomially solvable cases and the remaining cases which are \(\mathsf {NP}\)-complete. We characterise graphs with \(\lambda \le 4\) which leads to a polynomial-time algorithm recognizing the class and we show \(\mathsf {NP}\)-completeness for \(\lambda \ge 5\) by several reductions from Monotone Not All Equal 3-SAT.

Dušan Knop, Tomáš Masařík

1.5-Approximation Algorithm for the 2-Convex Recoloring Problem

Abstract

Given a graph \(G = (V, E)\), a coloring function \(\chi : V \rightarrow C\), assigning each vertex a color, is called convex if, for every color \(c \in C\), the set of vertices with color c induces a connected subgraph of G. In the Convex Recoloring problem a colored graph \(G_\chi \) is given, and the goal is to find a convex coloring \(\chi '\) of G that recolors a minimum number of vertices. The 2-Convex Recoloring problem (2-CR) is the special case, where the given coloring \(\chi \) assigns the same color to at most two vertices. 2-CR is known to be NP-hard even if G is a path.

We show that weighted 2-CR problem cannot be approximated within any ratio, unless P \(=\) NP. On the other hand, we provide an alternative definition of (unweighted) 2-CR in terms of maximum independent set of paths, which leads to a natural greedy algorithm. We prove that its approximation ratio is \(\frac{3}{2}\) and show that this analysis is tight. This is the first constant factor approximation algorithm for a variant of CR in general graphs. For the special case, where G is a path, the algorithm obtains a ratio of \(\frac{5}{4}\), an improvement over the previous best known approximation. We also consider the problem of determining whether a given graph has a convex recoloring of size k. We use the above mentioned characterization of 2-CR to show that a problem kernel of size 4k can be obtained in linear time and to design a \(O(|E|) + 2^{O(k \log k)}\) time algorithm for parametrized 2-CR.

Reuven Bar-Yehuda, Gilad Kutiel, Dror Rawitz

Computing the BWT and the LCP Array in Constant Space

Abstract

We show how to modify the in-place Burrows-Wheeler transform (\(\mathsf {BWT}\)) algorithm proposed by Crochemore et al. [4, 5] to also compute the longest common prefix (\(\mathsf {LCP}\)) array. Our algorithm runs in quadratic time, as its predecessor, constructing both the BWT and the LCP array using just O(1) additional space. It is supported by interesting properties of the \(\mathsf {BWT}\) and of the \(\mathsf {LCP}\) array and inherits its predecessor simplicity.

Felipe A. Louza, Guilherme P. Telles

EERTREE: An Efficient Data Structure for Processing Palindromes in Strings

Abstract

We propose a new linear-size data structure which provides a fast access to all palindromic substrings of a string or a set of strings. This structure inherits some ideas from the construction of both the suffix trie and suffix tree. Using this structure, we present simple and efficient solutions for a number of problems involving palindromes.

Mikhail Rubinchik, Arseny M. Shur

On the Zero Forcing Number of Bijection Graphs

Abstract

The zero forcing number of a graph is a graph parameter based on a color change process, which starts with a state, where all vertices are colored either black or white. In the next step a white vertex turns black, if it is the only white neighbor of some black vertex, and this step is then iterated. The zero forcing number Z(G) is defined as the minimum cardinality of a set S of black vertices such that the whole vertex set turns black.

In this paper we study Z(G) for the class of bijection graphs, where a bijection graph is a graph on 2n vertices that can be partitioned into two parts with n vertices each, joined by a perfect matching. For this class of graphs we show an upper bound for the zero forcing number and classify the graphs that attain this bound. We improve the general lower bound for the zero forcing number, which is \(Z(G)\ge \delta (G)\), for certain bijection graphs and use this improved bound to find the exact value of the zero forcing number for these graphs. This extends and strengthens results of Yi (2012) about the more restricted class of so called permutation graphs.

Denys Shcherbak, Gerold Jäger, Lars-Daniel Öhman

The k-Leaf Spanning Tree Problem Admits a Klam Value of 39

Abstract

The klam value of an algorithm that runs in time \(O^*(f(k))\) is the maximal value k such that \(f(k)<10^{20}\). Given a graph G and a parameter k, the k -Leaf Spanning Tree ( k -LST) problem asks if G contains a spanning tree with at least k leaves. This problem has been extensively studied over the past three decades. In 2000, Fellows et al. [FSTTCS’00] asked whether it admits a klam value of 50. A steady progress towards an affirmative answer continued until 5 years ago, when an algorithm of klam value 37 was discovered. Our contribution is twofold. First, we present an \(O^*(3.188^k)\)-time parameterized algorithm for k -LST, which shows that the problem admits a klam value of 39. Second, we rely on an application of the bounded search trees technique where the correctness of rules crucially depends on the history of previously applied rules in a non-standard manner, encapsulated in a “dependency claim”. Similar claims may be used to capture the essence of other complex algorithms in a compact, useful manner.

Meirav Zehavi

Backmatter