Search

Graph modification problems typically ask for a small set of operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the same property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem that allows all three types of operations: given a graph and integers , and , the chordal editing problem asks whether can be transformed into a chordal graph by at most vertex deletions, edge deletions, and edge additions. Clearly, this problem generalizes both chordal deletion and chordal completion (also known as minimum fill- in). Our main result is an algorithm for chordal editing in time , where and is the number of vertices of . Therefore, the problem is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm is both more efficient and conceptually simpler than the previously known algorithm for the special case chordal deletion. [ABSTRACT FROM AUTHOR]

We give an algorithm for computing the directed pathwidth of a digraph with n vertices in $$O(1.89^{n})$$ time. This is the first algorithm with running time better than the straightforward $$O^{*}(2^n)$$ . As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in $$O(1.9657^n)$$ time. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a connected $$P_k$$ -free graph, $$k \ge 4$$ . We show that $$G$$ admits a connected dominating set that induces either a $$P_{k-2}$$ -free graph or a graph isomorphic to $$P_{k-2}$$ . In fact, every minimum connected dominating set of $$G$$ has this property. This yields a new characterization for $$P_k$$ -free graphs: a graph $$G$$ is $$P_k$$ -free if and only if each connected induced subgraph of $$G$$ has a connected dominating set that induces either a $$P_{k-2}$$ -free graph, or a graph isomorphic to $$C_k$$ . We present an efficient algorithm that, given a connected graph $$G$$ , computes a connected dominating set $$X$$ of $$G$$ with the following property: for the minimum $$k$$ such that $$G$$ is $$P_k$$ -free, the subgraph induced by $$X$$ is $$P_{k-2}$$ -free or isomorphic to $$P_{k-2}$$ . As an application our results, we prove that Hypergraph 2- Colorability can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graphs is $$P_7$$ -free. [ABSTRACT FROM AUTHOR]

A graph is outer 1-planar ( o1p) if it can be drawn in the plane such that all vertices are in the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time, and specialize 1-planar graphs, whose recognition is $${NP}$$ -hard. We explore o1p graphs. Our first main result is a linear-time algorithm that takes a graph as input and returns a positive or a negative witness for o1p. If a graph $$G$$ is o1p, then the algorithm computes an embedding and can augment $$G$$ to a maximal o1p graph. Otherwise, $$G$$ includes one of six minors, which is detected by the recognition algorithm. Secondly, we establish structural properties of o1p graphs. o1p graphs are planar and are subgraphs of planar graphs with a Hamiltonian cycle. They are neither closed under edge contraction nor under subdivision. Several important graph parameters, such as treewidth, colorability, stack number, and queue number, increase by one from outerplanar to o1p graphs. Every o1p graph of size $$n$$ has at most $$\frac{5}{2} n - 4$$ edges and there are maximal o1p graphs with $$\frac{11}{5} n - \frac{18}{5}$$ edges, and these bounds are tight. Finally, every o1p graph has a straight-line grid drawing in $$\fancyscript{O}(n^2)$$ area with all vertices in the outer face, a planar visibility representation in $$\fancyscript{O}(n \log n)$$ area, and a 3D straight-line drawing in linear volume, and these drawings can be constructed in linear time. [ABSTRACT FROM AUTHOR]

We present original average-case results on the performance of the Ford-Fulkerson maxflow algorithm on grid graphs (sparse) and random geometric graphs (dense). The analysis technique combines experiments with probability generating functions, stochastic context free grammars and an application of the maximum likelihood principle enabling us to make statements about the performance, where a purely theoretical approach has little chance of success. The methods lends itself to automation allowing us to study more variations of the Ford-Fulkerson maxflow algorithm with different graph search strategies and several elementary operations. A simple depth-first search enhanced with random iterators provides the best performance on grid graphs. For random geometric graphs a simple priority-first search with a maximum-capacity heuristic provides the best performance. Notable is the observation that randomization improves the performance even when the inputs are created from a random process. [ABSTRACT FROM AUTHOR]

Stackelberg pricing of vertex covers in a bipartite graph, with the priceable nodes on one side of the bipartition, reduces to a sequence of maximum flow problems. This was shown by Briest et al. (Algorithmica 62:733-753, ), leading to an $$O(n^6)$$ algorithm. Here $$n$$ is the number of nodes of the graph. We show how the use of the preflow algorithm gives an $$O(n^4)$$ algorithm. [ABSTRACT FROM AUTHOR]

We consider a hybrid two-stage optimization problem that generalizes two classic combinatorial optimization problems: (i) weighted vertex cover in graphs, and (ii) makespan minimization in multiprocessor scheduling. An instance specifies a machine environment, a set of jobs, and an undirected graph over the jobs. The goal is to select a subset of the jobs that forms a vertex cover and to schedule it on a set of parallel machines so as to minimize the makespan. We call this problem family vertex cover meets multiprocessor scheduling (VCMS). The problem is motivated by networks where vertices represent servers and each edge corresponds to a task that can be done by any of the two servers of its endpoint. Each selected server can complete any number of tasks assigned to it within a given time defined by its weight, as the time consumption of the server is roughly equal to its activation time. The activation is performed by a set of $$m$$ processors, such that every selected server is activated by one processor, and the goal is to minimize the maximum total activation time assigned to any processor. We design a multitude of approximation algorithms for VCMS and its variants, many of which match or almost match the best approximation bound known for the vertex cover problem. In particular, we give a $$2$$ -approximation for the case of a fixed number of unrelated machines, a $$3$$ -approximation for an arbitrary number of unrelated machines, and a $$(2+\varepsilon )$$ -approximation for an arbitrary number of identical machines. Furthermore we consider special graph classes for which the weighted vertex cover problem can be solved to optimality in polynomial time: for many of these classes, there is a PTAS for VCMS on identical machines; for bipartite graphs, however, VCMS on identical machines turns out to be APX-hard. Finally, we study the bin packing counterpart of VCMS and design a $$(2+\varepsilon )$$ -approximation algorithm for it. [ABSTRACT FROM AUTHOR]

We study parameterized complexity of a generalization of the classical Feedback Vertex Set problem, namely the Group Feedback Vertex Set problem: we are given a graph $$G$$ with edges labeled with group elements, and the goal is to compute the smallest set of vertices that hits all cycles of $$G$$ that evaluate to a non-null element of the group. This problem generalizes not only Feedback Vertex Set, but also Subset Feedback Vertex Set, Multiway Cut and Odd Cycle Transversal . Completing the results of Guillemot (Discrete Optim 8(1):61-71, ), we provide a fixed-parameter algorithm for the parameterization by the size of the cutset only. Our algorithm works even if the group is given as a blackbox performing group operations. [ABSTRACT FROM AUTHOR]

We show that the following two problems are fixed-parameter tractable with parameter $$k$$ : testing whether a connected $$n$$ -vertex graph with $$m$$ edges has a square root with at most $$n-1+k$$ edges and testing whether such a graph has a square root with at least $$m-k$$ edges. Our first result implies that squares of graphs obtained from trees by adding at most $$k$$ edges can be recognized in polynomial time for every fixed $$k\ge 0$$ ; previously this result was known only for $$k=0$$ . Our second result is equivalent to stating that deciding whether a graph can be modified into a square root of itself by at most $$k$$ edge deletions is fixed-parameter tractable with parameter $$k$$ . [ABSTRACT FROM AUTHOR]

We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant $$l$$ , outputs a directed Steiner tree of cost no larger than $$2(l-1)(\ln n+1)$$ times the cost of any $$l$$ -restricted Steiner tree, which is such a Steiner tree in which every terminal is at most $$l$$ arcs away from the root or another terminal. We derive from this result that (1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of $$O(\log n)$$ , and (2) the tree cover problem on directed graphs can also be approximated within a factor of $$O(\log n)$$ . [ABSTRACT FROM AUTHOR]

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. An initial configuration of agents is called gatherable if there exists a deterministic algorithm (even dedicated to this particular configuration) that achieves meeting of all agents in one node. Which configurations are gatherable and how to gather all of them deterministically by the same algorithm? We give a complete solution of this gathering problem in arbitrary networks. We characterize all gatherable configurations and give two universal deterministic gathering algorithms, i.e., algorithms that gather all gatherable configurations. The first algorithm works under the assumption that a common upper bound $$N$$ on the size of the network is known to all agents. In this case our algorithm guarantees gathering with detection, i.e., the existence of a round for any gatherable configuration, such that all agents are at the same node and all declare that gathering is accomplished. If no upper bound on the size of the network is known, we show that a universal algorithm for gathering with detection does not exist. Hence, for this harder scenario, we construct a second universal gathering algorithm, which guarantees that, for any gatherable configuration, all agents eventually get to one node and stop, although they cannot tell if gathering is over. The time of the first algorithm is polynomial in the upper bound $$N$$ on the size of the network, and the time of the second algorithm is polynomial in the (unknown) size itself. Our results have an important consequence for the leader election problem for anonymous agents in arbitrary graphs. Leader election is a fundamental symmetry breaking problem in distributed computing. Its goal is to assign, in some common round, value 1 (leader) to one of the entities and value 0 (non-leader) to all others. For anonymous agents in graphs, leader election turns out to be equivalent to gathering with detection. Hence, as a by-product, we obtain a complete solution of the leader election problem for anonymous agents in arbitrary graphs. [ABSTRACT FROM AUTHOR]

We introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. The polynomials are assumed to have coefficients from a field of characteristic two. As applications of the technique, we show an $$O^*(2^k)$$ -time polynomial space algorithm for the $$k$$ -sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min- Substitute Graph Motif, and Min- Add Graph Motif. Finally, we provide a piece of evidence that our result might be essentially tight: the existence of an $$O^*((2-\epsilon )^k)$$ -time algorithm for the Graph Motif problem implies an $$O((2-\epsilon ')^n)$$ -time algorithm for Set Cover. [ABSTRACT FROM AUTHOR]

Given an interval graph and integer $$k$$ , we consider the problem of finding a subgraph of size $$k$$ with a maximum number of induced edges, called densest k -subgraph problem in interval graphs. This problem is NP-hard even for chordal graphs (Perl and Corneil in Discret Appl Math 9(1):27-39, ), and there is probably no PTAS for general graphs (Khot and Subhash in SIAM J Comput 36(4):1025-1071, ). However, the exact complexity status for interval graphs is a long-standing open problem (Perl and Corneil in Discret Appl Math 9(1):27-39, ), and the best known approximation result is a $$ 3 $$ -approximation algorithm (Liazi et al. in Inf Process Lett 108(1):29-32, ). We shed light on the approximation complexity of finding a densest $$ k $$ -subgraph in interval graphs by presenting a polynomial-time approximation scheme (PTAS), that is, we show that there is an $$ (1+\epsilon ) $$ -approximation algorithm for any $$ \epsilon > 0 $$ , which is the first such approximation scheme for the densest $$ k $$ -subgraph problem in an important graph class without any further restrictions. [ABSTRACT FROM AUTHOR]

A graph drawn in the plane with $$n$$ vertices is $$k$$ -fan-crossing free for $$k \geqslant 2$$ if there are no $$k+1$$ edges $$g,e_1,\ldots , e_k$$ , such that $$e_1,e_2,\ldots ,e_k$$ have a common endpoint and $$g$$ crosses all $$e_i$$ . We prove a tight bound of $$4n-8$$ on the maximum number of edges of a $$2$$ -fan-crossing free graph, and a tight $$4n-9$$ bound for a straight-edge drawing. For $$k \geqslant 3$$ , we prove an upper bound of $$3(k-1)(n-2)$$ edges. We also discuss generalizations to monotone graph properties. [ABSTRACT FROM AUTHOR]

A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph $$G$$ , denoted by $$\chi _b(G)$$ , is the maximum number $$t$$ such that $$G$$ admits a b-coloring with $$t$$ colors. A graph $$G$$ is called b-continuous if it admits a b-coloring with $$t$$ colors, for every $$t = \chi (G),\ldots ,\chi _b(G)$$ , and b-monotonic if $$\chi _b(H_1) \ge \chi _b(H_2)$$ for every induced subgraph $$H_1$$ of $$G$$ , and every induced subgraph $$H_2$$ of $$H_1$$ . We investigate the b-chromatic number of graphs with stability number two. These are exactly the complements of triangle-free graphs, thus including all complements of bipartite graphs. The main results of this work are the following: (1) We characterize the b-colorings of a graph with stability number two in terms of matchings with no augmenting paths of length one or three. We derive that graphs with stability number two are b-continuous and b-monotonic. (2) We prove that it is NP-complete to decide whether the b-chromatic number of co-bipartite graph is at least a given threshold. (3) We describe a polynomial time dynamic programming algorithm to compute the b-chromatic number of co-trees. (4) Extending several previous results, we show that there is a polynomial time dynamic programming algorithm for computing the b-chromatic number of tree-cographs. Moreover, we show that tree-cographs are b-continuous and b-monotonic. [ABSTRACT FROM AUTHOR]

We prove a general reduction theorem which allows us to extend bounds for certain graph parameters on cubic graphs to bounds for general graphs taking into account the individual vertex degrees. As applications, we give an algorithm for Max $$2$$ -CSP whose complexity matches the algorithm of Scott and Sorkin in the case of $$d$$ -regular graphs, $$d \le 5$$ , but is otherwise faster. It also improves on the previously fastest known algorithm in terms of the average degree, given by Golovnev and Kutzkov. Also from the general theorem, we derive a bound for the pathwidth of a general graph which equals that of Fomin et al. and Gaspers for graphs of degree at most $$6$$ , but is smaller otherwise, and use this to give an improved exponential-space algorithm for Max $$2$$ -CSP. Finally we use the general result to give a faster algorithm for Max $$2$$ -CSP on claw-free graphs. [ABSTRACT FROM AUTHOR]

We study the following optimization problem. The input is a number $$k$$ and a directed graph with a specified 'start' vertex, each of whose vertices may have one 'memory bank requirement', an integer. There are $$k$$ 'registers', labeled $$1, \ldots , k$$ . A valid solution associates to the vertices with no bank requirement one or more 'load instructions' $$L[b,j]$$ , for bank $$b$$ and register $$j$$ , such that every directed trail from the start vertex to some vertex with bank requirement $$c$$ contains a vertex $$u$$ that has been associated $$L[c,i]$$ (for some register $$i \le k$$ ) and no vertex following $$u$$ in the trail has been associated an $$L[b,i]$$ , for any other bank $$b$$ . The objective is to minimize the total number of associated load instructions. We give a $$k(k+1)$$ -approximation algorithm based on linear programming rounding, with $$(k+1)$$ being the best possible unless Vertex Cover has approximation $$2 - {\epsilon }$$ for $${\epsilon }> 0$$ . We also present a $$O(k \log n)$$ approximation, with $$n$$ being the number of vertices in the input directed graph. Based on the same linear program, another rounding method outputs a valid solution with objective at most $$2k$$ times the optimum for $$k$$ registers, using $$2k-1$$ registers. [ABSTRACT FROM AUTHOR]

Let ε, ε be two non negative numbers. An approximate rectangle of influence drawing (also called ( ε, ε)-RID) is a proximity drawing of a graph such that: (i) if u, v are adjacent vertices then their rectangle of influence 'scaled down' by the factor $\frac{1}{1+\varepsilon_{1}}$ does not contain other vertices of the drawing; (ii) if u, v are not adjacent, then their rectangle of influence 'blown-up' by the factor 1+ ε contains some vertices of the drawing other than u and v. Firstly, we prove that all planar graphs have an ( ε, ε)-RID for any ε>0 and ε>0, while there exist planar graphs which do not admit an ( ε,0)-RID and planar graphs which do not admit a (0, ε)-RID. Then, we investigate (0, ε)-RIDs; we prove that both the outerplanar graphs and a suitably defined family of graphs without separating 3-cycles admit this type of drawing. Finally, we study polynomial area approximate rectangle of influence drawings and prove that (0, ε)-RIDs of proper track planar graphs (a superclass of the outerplanar graphs) can be computed in polynomial area for any ε>2. As for values of ε such that ε≤2, we describe a drawing algorithm that computes (0, ε)-RIDs of binary trees in area $O(n^{c + f(\varepsilon_{2})})$, where c is a positive constant, f( ε) is a poly-logarithmic function that tends to infinity as ε tends to zero, and n is the number of vertices of the input tree. [ABSTRACT FROM AUTHOR]

Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for t-interval graphs when t≥3 and polynomial-time solvable when t=1. The problem is also known to be NP-complete in t-track graphs when t≥4 and polynomial-time solvable when t≤2. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called t-circular interval graphs and t-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time t-approximation algorithm for MAXIMUM WEIGHTED CLIQUE on t-interval graphs, improving earlier work with approximation ratio 4 t. [ABSTRACT FROM AUTHOR]

Monge matrices play a fundamental role in optimisation theory, graph and string algorithms. Distance multiplication of two Monge matrices of size n can be performed in time O( n). Motivated by applications to string algorithms, we introduced in previous works a subclass of Monge matrices, that we call simple unit-Monge matrices. We also gave a distance multiplication algorithm for such matrices, running in time O( n). Landau asked whether this problem can be solved in linear time. In the current work, we give an algorithm running in time O( nlog n), thus approaching an answer to Landau's question within a logarithmic factor. The new algorithm implies immediate improvements in running time for a number of algorithms on strings and graphs. In particular, we obtain an algorithm for finding a maximum clique in a circle graph in time O( nlog n), and a surprisingly efficient algorithm for comparing compressed strings. We also point to potential applications in group theory, by making a connection between unit-Monge matrices and Coxeter monoids. We conclude that unit-Monge matrices are a fascinating object and a powerful tool, that deserve further study from both the mathematical and the algorithmic viewpoints. [ABSTRACT FROM AUTHOR]

We present a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. The allowed operations on the graph involve the insertion and removal of vertices (together with its incident edges) or edges. Edge operations cost O(log n) time, where n is the number of vertices of the graph, while vertex operations cost O(log n+ d) time, where d is the degree of the modified vertex. We also show incremental and decremental algorithms that work in O(1) time per inserted or removed edge. As part of our algorithm, fully dynamic connectivity and co-connectivity algorithms that work in O(log n) time per operation are obtained. Also, an O(Δ) time algorithm for determining if a PCA representation corresponds to a co-bipartite graph is provided, where Δ is the maximum among the degrees of the vertices. When the graph is co-bipartite, a co-bipartition of each of its co-components is obtained within the same amount of time. As an application, we show how to find a minimal forbidden induced subgraph of a static graph in O( n+ m) time. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of a broad class of problems called 'local graph partitioning problems' that includes the classical fixed cardinality problems as max $$k$$ - vertex cover, $$k$$ - densest subgraph, etc. By developing a technique that we call 'greediness-for-parameterization', we obtain fixed parameter algorithms with respect to a pair of parameters $$k$$ , the size of the solution (but not its value) and $$\varDelta $$ , the maximum degree of the input graph. In particular, greediness-for-parameterization improves asymptotic running times for these problems upon random separation (that is a special case of color coding) and is more intuitive and simple. Then, we show how these results can be easily extended for getting standard-parameterization results (i.e., with parameter the value of the optimal solution) for a well known local graph partitioning problem. [ABSTRACT FROM AUTHOR]

We investigate whether an $$n$$ -vertex instance $$(G,k)$$ of Treewidth, asking whether the graph $$G$$ has treewidth at most $$k$$ , can efficiently be made sparse without changing its answer. By giving a special form of $$\mathop {\mathrm {\textsc {or}}}$$ -cross-composition, we prove that this is unlikely: if there is an $$\epsilon > 0$$ and a polynomial-time algorithm that reduces $$n$$ -vertex Treewidth instances to equivalent instances, of an arbitrary problem, with $$\mathcal {O} (n^{2 - \epsilon })$$ bits, then NP $$\subseteq $$ coNP $$/$$ poly and the polynomial hierarchy collapses to its third level. Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures $$\ell $$ that do not exceed the number of vertices cannot have kernels with $$\mathcal {O} (\ell ^{2 - \epsilon })$$ bits for any $$\epsilon > 0$$ , unless NP $$\subseteq $$ coNP $$/$$ poly. Motivated by the question of determining the optimal kernel size for Treewidth parameterized by the size of a vertex cover $$X$$ , we improve the $$\mathcal {O} (|X|^3)$$ -vertex kernel from Bodlaender et al. (SIDMA ) to a kernel with $$\mathcal {O} (|X|^2)$$ vertices. Our improved kernel is based on the novel notion of treewidth-invariant set. We use the $$q$$ -expansion lemma of Fomin et al. (STACS ) to find such sets efficiently in graphs whose order is superquadratic in their vertex cover number. We believe that our new reduction rule will be useful in practice. [ABSTRACT FROM AUTHOR]

We treat PNE-GG, the problem of deciding the existence of a Pure Nash Equilibrium in a graphical game, and the role of treewidth in this problem. PNE-GG is known to be $$NP$$ -complete in general, but polynomially solvable for graphical games of bounded treewidth. We prove that PNE-GG is $$W[1]$$ -Hard when parameterized by treewidth. On the other hand, we give a dynamic programming approach that solves the problem in $$O^*(\alpha ^w)$$ time, where $$\alpha $$ is the cardinality of the largest strategy set and $$w$$ is the treewidth of the input graph (and $$O^*$$ hides polynomial factors). This proves that PNE-GG is in $$FPT$$ for the combined parameter $$(\alpha ,w)$$ . Moreover, we prove that there is no algorithm that solves PNE-GG in $$O^*((\alpha -\epsilon )^w)$$ time for any $$\epsilon > 0$$ , unless the Strong Exponential Time Hypothesis fails. Our lower bounds implicitly assume that $$\alpha \ge 3$$ ; we show that for $$\alpha =2$$ the problem can be solved in polynomial time. Finally, we discuss the implication for computing pure Nash equilibria in graphical games (PNE-GG) of $$O(\log n)$$ treewidth, the existence of polynomial kernels for PNE-GG parameterized by treewidth, and the construction of a sample and maximum-payoff pure Nash equilibrium. [ABSTRACT FROM AUTHOR]

A binary matrix $$M$$ has the Consecutive Ones Property (COP) if there exists a permutation of columns that arranges the ones consecutively in all the rows. We consider the parameterized complexity of $$d$$ -COS-R (Consecutive Ones Submatrix by Row deletions) problem []: Given a matrix $$M$$ and a positive integer $$d$$ , decide whether there exists a set of at most $$d$$ rows of $$M$$ whose deletion results in a matrix with the COP. The closely related Interval Deletion problem has recently been shown to be FPT []. We show that $$d$$ -COS-R is fixed-parameter tractable and has the current best run-time of $$O^*(10^d)$$ , which is associated with the Interval Deletion problem. We also introduce a closely related optimization problem called Min-ICPSA: For a finite sized universe $$\mathcal{U}$$ the input consists of a family of $$n$$ pairs of sets $$\mathcal{S} = \{(A_i,B_i) \mid A_i, B_i \subseteq \mathcal{U}, 1 \le i \le n\}$$ ; the aim is to find a minimum number of pairs of sets to discard from $$\mathcal{S}$$ such that for each one of the remaining pairs, say $$(A_k,B_k), |A_k|=|B_k|$$ , and for any two of the remaining pairs, indexed by $$1 \le j \ne k \le n$$ , $$|A_j \cap A_k| = |B_j \cap B_k|$$ . We show that Min-ICPSA is computationally equivalent to the Vertex Cover problem. We also show that it is at least as hard as the Hamilton Path problem in undirected graphs, even when each $$|A_k|=2, 1 \le k \le n$$ . [ABSTRACT FROM AUTHOR]

The k-feedback arc set problem is to determine whether there is a set F of at most k arcs in a directed graph G such that the removal of F makes G acyclic. The k-feedback arc set problems in tournaments and bipartite tournaments ( k-FAST and k-FASBT) have applications in ranking aggregation and have been extensively studied from the viewpoint of parameterized complexity. By introducing a new concept called 'bimodule', we provide a problem kernel with O( k) vertices for k-FASBT, which improves the previous result by a factor of k. [ABSTRACT FROM AUTHOR]

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism, denoted CHI, which has running time (2 N), where the parameter b is the maximum size of the color classes of the given hypergraphs and N is the input size. We also describe an fpt algorithm for a parameterized coset intersection problem that is used as a subroutine in our algorithm for CHI. [ABSTRACT FROM AUTHOR]

The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop kernelization algorithms for the problem on several classes of sparse graphs. We obtain linear kernels on planar graphs, and kernels of size $\mathcal {O}(k^{3/2})$ in graphs excluding some fixed graph as a minor and in graphs of bounded degeneracy. As a byproduct of our results, we obtain approximation algorithms with approximation ratios $\mathcal {O}(\log{k})$ on planar graphs and $\mathcal {O}(\sqrt{k}\log{k})$ on H-minor-free graphs. These results significantly improve the previously known kernelization and approximation results for Minimum Fill-in on sparse graphs. [ABSTRACT FROM AUTHOR]

The article focuses on the papers presented in the periodical related to the 18th Annual International Computing and Combinatorics Conference (COCOON), held during August 20-22, 2012, in Sydney, Australia. It states that conferences discusses topics related to theoretical aspects of computing and from clustering to circuit lower bounds.

It is shown that for cuckoo hashing with a stash as proposed by Kirsch et al. (Proc. 16th European Symposium on Algorithms (ESA), pp. 611-622, Springer, Berlin, ) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with constant stash size s the probability of a rehash is O(1/ n), the lookup time and the deletion time are O( s) in the worst case, and the amortized expected insertion time is O( s) as well. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (Discrete Math. Theor. Comput. Sci., 12(3):81-102, ) (resp. Θ(log n)-wise independence for standard cuckoo hashing) the new approach even works with 2-wise independent hash families as building blocks. Both construction and analysis build upon the work of Dietzfelbinger and Woelfel (Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 629-638, ). The analysis, which can also be applied to the fully random case, utilizes a graph counting argument and is much simpler than previous proofs. The results can be generalized to situations where the stash size is non-constant. [ABSTRACT FROM AUTHOR]

We consider the (precedence constrained) Minimum Feedback Arc Set problem with triangle inequalities on the weights, which finds important applications in problems of ranking with inconsistent information. We present a surprising structural insight showing that the problem is a special case of the minimum vertex cover in hypergraphs with edges of size at most 3. [ABSTRACT FROM AUTHOR]

Circulant graphs are regular graphs based on Cayley graphs defined on the Abelian group $\mathbb{Z}_{n}$. They are popular network topologies that arise in distributed computing. Using number theoretical tools, we first prove two main results for random directed k-regular circulant graphs with n vertices, when n is sufficiently large and k is fixed. First, for any fixed ε>0, n= p prime and L≥ p(log p), walks of length at most L terminate at every vertex with asymptotically the same probability. Second, for any n, there is a polynomial time algorithm that for almost all undirected 2 r-regular circulant graphs finds a vertex bisector and an edge bisector, both of size less than n. We then prove that the latter result also holds for all (rather than for almost all) 2 r-regular circulant graphs with n= p, prime, vertices, while, in general, it does not hold for composite n. Using the bisection results, we provide lower bounds on the number of rounds required by any gossiping algorithms for any n. We introduce generic distributed algorithms to solve the gossip problem in any circulant graphs. We illustrate the efficiency of these algorithms by giving nearly matching upper bounds of the number of rounds required by these algorithms in the vertex-disjoint and the edge-disjoint paths communication models in particular circulant graphs. [ABSTRACT FROM AUTHOR]

We consider Degree Constrained Survivable Network problems. For the directed Degree Constrained k -Edge-Outconnected Subgraph problem, we slightly improve the best known approximation ratio, by a simple proof. Our main contribution is giving a framework to handle node-connectivity degree constrained problems with the iterative rounding method. In particular, for the degree constrained versions of the Element-Connectivity Survivable Network problem on undirected graphs, and of the k -Outconnected Subgraph problem on both directed and undirected graphs, our algorithm computes a solution J of cost O(log k) times the optimal, with degrees O(2)⋅ b( v). Similar result are obtained for the k -Connected Subgraph problem. The latter improves on the only degree approximation O( klog n)⋅ b( v) in O( n) time on undirected graphs by Feder, Motwani, and Zhu. [ABSTRACT FROM AUTHOR]

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[ 1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs. [ABSTRACT FROM AUTHOR]

Minimum witnesses for Boolean matrix multiplication play an important role in several graph algorithms. For two Boolean matrices A and B of order n, with one of the matrices having at most m nonzero entries, the fastest known algorithms for computing the minimum witnesses of their product run in either O( n) time or in O( n+ mnlog( n/ m)/log n) time. We present a new algorithm for this problem. Our algorithm runs either in time where ω<2.376 is the matrix multiplication exponent, or, if fast rectangular matrix multiplication is used, in time In particular, if ω−1< α<2 where m= n, the new algorithm is faster than both of the aforementioned algorithms. [ABSTRACT FROM AUTHOR]

For any angle α<2 π, we show that any connected communication graph that is induced by a set P of n transceivers using omni-directional antennas of radius 1, can be replaced by a strongly connected communication graph, in which each transceiver in P is equipped with a directional antenna of angle α and radius r, for some constant r= r( α). Moreover, the new communication graph is a c-spanner of the original graph, for some constant c= c( α), with respect to number of hops. [ABSTRACT FROM AUTHOR]

We present a data structure that stores a sequence s[1.. n] over alphabet [1.. σ] in $n\mathcal{H}_{0}(s) + o(n)(\mathcal {H}_{0}(s){+}1)$ bits, where $\mathcal{H}_{0}(s)$ is the zero-order entropy of s. This structure supports the queries access, rank and select, which are fundamental building blocks for many other compressed data structures, in worst-case time ${\mathcal{O} ( {\lg\lg\sigma} )}$ and average time ${\mathcal{O} ( {\lg\mathcal{H}_{0}(s)} )}$. The worst-case complexity matches the best previous results, yet these had been achieved with data structures using $n\mathcal{H}_{0}(s)+o(n\lg \sigma)$ bits. On highly compressible sequences the o( nlg σ) bits of the redundancy may be significant compared to the $n\mathcal{H}_{0}(s)$ bits that encode the data. Our representation, instead, compresses the redundancy as well. Moreover, our average-case complexity is unprecedented. Our technique is based on partitioning the alphabet into characters of similar frequency. The subsequence corresponding to each group can then be encoded using fast uncompressed representations without harming the overall compression ratios, even in the redundancy. The result also improves upon the best current compressed representations of several other data structures. For example, we achieve (i) compressed redundancy, retaining the best time complexities, for the smallest existing full-text self-indexes; (ii) compressed permutations π with times for π() and π() improved to loglogarithmic; and (iii) the first compressed representation of dynamic collections of disjoint sets. We also point out various applications to inverted indexes, suffix arrays, binary relations, and data compressors. Our structure is practical on large alphabets. Our experiments show that, as predicted by theory, it dominates the space/time tradeoff map of all the sequence representations, both in synthetic and application scenarios. [ABSTRACT FROM AUTHOR]

Preemptive scheduling problems on parallel machines are classic problems. Given the goal of minimizing the makespan, they are polynomially solvable even for the most general model of unrelated machines. In these problems, a set of jobs is to be assigned to run on a set of m machines. A job can be split into parts arbitrarily and these parts are to be assigned to time slots on the machines without parallelism, that is, for every job, at most one of its parts can be processed at each time. Motivated by sensitivity analysis and online algorithms, we investigate the problem of designing robust algorithms for constructing preemptive schedules. Robust algorithms receive one piece of input at a time. They may change a small portion of the solution as an additional part of the input is revealed. The capacity of change is based on the size of the new piece of input. For scheduling problems, the supremum ratio between the total size of the jobs (or parts of jobs) which may be re-scheduled upon the arrival of a new job j, and the size of j, is called migration factor. We design a strongly optimal algorithm with the migration factor $1-\frac{1}{m}$ for identical machines. Strongly optimal algorithms avoid idle time and create solutions where the (non-increasingly) sorted vector of completion times of the machines is lexicographically minimal. In the case of identical machines this results not only in makespan minimization, but the created solution is also optimal with respect to any ℓ norm (for p>1). We show that an algorithm of a smaller migration factor cannot be optimal with respect to makespan or any other ℓ norm, thus the result is best possible in this sense as well. We further show that neither uniformly related machines nor identical machines with restricted assignment admit an optimal algorithm with a constant migration factor. This lower bound holds both for makespan minimization and for any ℓ norm. Finally, we analyze the case of two machines and show that in this case it is still possible to maintain an optimal schedule with a small migration factor in the cases of two uniformly related machines and two identical machines with restricted assignment. [ABSTRACT FROM AUTHOR]

For directed and undirected graphs, we study how to make a distinguished vertex the unique minimum-(in)degree vertex through deletion of a minimum number of vertices. The corresponding NP-hard optimization problems are motivated by applications concerning control in elections and social network analysis. Continuing previous work for the directed case, we show that the problem is W[2]-hard when parameterized by the graph's feedback arc set number, whereas it becomes fixed-parameter tractable when combining the parameters 'feedback vertex set number' and 'number of vertices to delete'. For the so far unstudied undirected case, we show that the problem is NP-hard and W[1]-hard when parameterized by the 'number of vertices to delete'. On the positive side, we show fixed-parameter tractability for several parameterizations measuring tree-likeness. In particular, we provide a dynamic programming algorithm for graphs of bounded treewidth and a vertex-linear problem kernel with respect to the parameter 'feedback edge set number'. On the contrary, we show a non-existence result concerning polynomial-size problem kernels for the combined parameter 'vertex cover number and number of vertices to delete', implying corresponding non-existence results when replacing vertex cover number by treewidth or feedback vertex set number. [ABSTRACT FROM AUTHOR]

A random geometric graph (RGG) is defined by placing n points uniformly at random in [0, n], and joining two points by an edge whenever their Euclidean distance is at most some fixed r. We assume that r is larger than the critical value for the emergence of a connected component with Ω( n) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of $\omega (\frac{\log n}{r^{d-1}} )$, their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ( n/ r) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ( n/ r+log n) rounds. [ABSTRACT FROM AUTHOR]

We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (defining the local search area) 'Edge Exchange' and 'Max-Shift'. We perform studies with respect to the distance measures 'Swap' and ' r-Swap', 'Reversal' and ' r-Reversal', and 'Edit', achieving both fixed-parameter tractability and W[1]-hardness results. In particular, from the parameterized reduction showing W[1]-hardness we infer running time lower bounds (based on the exponential time hypothesis) for all corresponding distance measures. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs. [ABSTRACT FROM AUTHOR]

We introduce and study the donation center location problem, which has an additional application in network testing and may also be of independent interest as a general graph-theoretic problem. Given a set of agents and a set of centers, where agents have preferences over centers and centers have capacities, the goal is to open a subset of centers and to assign a maximum-sized subset of agents to their most-preferred opened centers, while respecting the capacity constraints. We prove that in general, the problem is hard to approximate within n for any ϵ>0. In view of this, we investigate two special cases. In one, every agent has a bounded number of centers on its preference list, and in the other, all preferences are induced by a line-metric. We present constant-factor approximation algorithms for the former and exact polynomial-time algorithms for the latter. [ABSTRACT FROM AUTHOR]

Let G=( V, E) be an undirected unweighted graph. A path between any two vertices u, v∈ V is said to be t-approximate shortest path if its length is at most t times the length of the shortest path between u and v. We address the problem of building a compact data structure which can efficiently answer the following query for any u, v, x∈ V and t>1: We present data structures for the single source as well as all-pairs versions of this problem. The query time guaranteed by our data structures is optimal up to a constant factor. Moreover, the size of each of them nearly matches the size of the corresponding data structure with no failures. [ABSTRACT FROM AUTHOR]

We present an O( nlog n)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O( rnlog n) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general matching algorithm that runs in $O(\sqrt{n}m)$-time for graphs with m edges, whenever m= ω( rnlog n). [ABSTRACT FROM AUTHOR]

The coverability and boundedness problems for Petri nets are known to be Expspace-complete. Given a Petri net, we associate a graph with it. With the vertex cover number k of this graph and the maximum arc weight W as parameters, we show that coverability and boundedness are in ParaPspace. This means that these problems can be solved in space $\mathcal{O} ({\mathit{ef}}(k, W){\mathit{poly}}(n) )$, where ef( k, W) is some super-polynomial function and poly( n) is some polynomial in the size of the input n. We then extend the ParaPspace result to model checking a logic that can express some generalizations of coverability and boundedness. [ABSTRACT FROM AUTHOR]

The problems studied in this article originate from the Graph Motif problem introduced by Lacroix et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3(4):360-368, ) in the context of biological networks. The problem is to decide if a vertex-colored graph has a connected subgraph whose colors equal a given multiset of colors M. It is a graph pattern-matching problem variant, where the structure of the occurrence of the pattern is not of interest but the only requirement is the connectedness. Using an algebraic framework recently introduced by Koutis (Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5125, pp. 575-586, ) and Koutis and Williams (Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5555, pp. 653-664, ), we obtain new FPT algorithms for Graph Motif and variants, with improved running times. We also obtain results on the counting versions of this problem, proving that the counting problem is FPT if M is a set, but becomes # W[1]-hard if M is a multiset with two colors. Finally, we present an experimental evaluation of this approach on real datasets, showing that its performance compares favorably with existing software. [ABSTRACT FROM AUTHOR]

We study the problem of computing Nash equilibria in a two-player normal form (bimatrix) game from the perspective of parameterized complexity. Recent results proved hardness for a number of variants, when parameterized by the support size. We complement those results, by identifying three cases in which the problem becomes fixed-parameter tractable. Our results are based on a graph-theoretic representation of a bimatrix game, and on applying graph-theoretic tools on this representation. [ABSTRACT FROM AUTHOR]

A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. (SIAM J. Comput. 38:946-962, ). We also present a 0.64-approximation algorithm for the problem on node-weighted graphs. Finally, we present improved hardness of approximation results for the weighted (both edge-weighted and node-weighted) versions of the problem. Our algorithms use a non-linear rounding scheme, which might be of independent interest. [ABSTRACT FROM AUTHOR]

We investigate a special case of the Induced Subgraph Isomorphism problem, where both input graphs are interval graphs. We show the NP-hardness of this problem, and we prove fixed-parameter tractability of the problem with non-standard parameterization, where the parameter is the difference | V( G)|−| V( H)|, with G and H being the larger and the smaller input graph, respectively. Intuitively, we can interpret this problem as 'cleaning' the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We also prove W[1]-hardness for the standard parameterization where the parameter is | V( H)|. [ABSTRACT FROM AUTHOR]

An edge dominating set in a graph G=( V, E) is a subset of the edges D⊆ E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of minimum cardinality is NP-hard. We present a faster exact exponential time algorithm for this problem. Our algorithm uses O(1.3226) time and polynomial space. The algorithm combines an enumeration approach of minimal vertex covers in the input graph with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwisely. In each of these refinement steps, the worst cases in the measure and conquer analysis of the current algorithm are reconsidered and a new branching strategy is proposed on one of these worst cases. In this way a series of algorithms appears, each one slightly faster than the previous one, ending in the O(1.3226) time algorithm. For each algorithm in the series, we also give a lower bound on its running time. We also show that the related problems: minimum weight edge dominating set, minimum maximal matching and minimum weight maximal matching can be solved in O(1.3226) time and polynomial space using modifications of the algorithm for edge dominating set. In addition, we consider the matrix dominating set problem which we solve in O(1.3226) time and polynomial space for n× m matrices, and the parametrised minimum weight maximal matching problem for which we obtain an O(2.4179) time and space algorithm. [ABSTRACT FROM AUTHOR]