Search

A k-page upward book embedding (kUBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the vertices appear in a topological ordering along the spine of the book. The kUBE Testing problem, which asks whether a graph admits a kUBE, was introduced in 1999 by Heath, Pemmaraju, and Trenk (SIAM J Comput 28(4), 1999). In a companion paper, Heath and Pemmaraju (SIAM J Comput 28(5), 1999) proved that the problem is linear-time solvable for k = 1 and NP-complete for k = 6 . Closing this gap has been a central question in algorithmic graph theory since then. In this paper, we make a major contribution towards a definitive answer to the above question by showing that kUBE Testing is NP-complete for k ≥ 3 , even for st-graphs, i.e., acyclic directed graphs with a single source and a single sink. Indeed, our result, together with a recent work of Bekos et al. (Theor Comput Sci 946, 2023) that proves the NP-completeness of 2UBE for planar st-graphs, closes the question about the complexity of the kUBE problem for any k. Motivated by this hardness result, we then focus on the 2UBE Testing for planar st-graphs. On the algorithmic side, we present an O (f (β) · n + n 3) -time algorithm for 2UBE Testing, where β is the branchwidth of the input graph and f is a singly-exponential function on β . Since the treewidth and the branchwidth of a graph are within a constant factor from each other, this result immediately yields an FPT algorithm for st-graphs of bounded treewidth. Furthermore, we describe an O(n)-time algorithm to test whether a plane st-graph whose faces have a special structure admits a 2UBE that additionally preserves the plane embedding of the input st-graph. On the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving 2 UBE. [ABSTRACT FROM AUTHOR]

An introduction to the journal is presented which discusses various papers published within the issue, including "Boxicity and Separation Dimension," "A New Characterization of Pk-Free Graphs" and "Between Treewidth and Clique-Width."

The (directed) metric dimension of a digraph D, denoted by MD → (D) , is the size of a smallest subset S of vertices such that every two vertices of D are distinguished via their distances from the vertices in S. In this paper, we investigate the graph parameters BOMD (G) and WOMD (G) which are respectively the smallest and largest metric dimension over all orientations of G. We show that those parameters are related to several classical notions of graph theory and investigate the complexity of determining those parameters. We show that BOMD (G) = 1 if and only if G is hypotraceable (that is has a path spanning all vertices but one), and deduce that deciding whether BOMD (G) ≤ k is NP-complete for every positive integer k. We also show that WOMD (G) ≥ α (G) - 1 , where α (G) is the stability number of G. We then deduce that for every fixed positive integer k, we can decide in polynomial time whether WOMD (G) ≤ k . The most significant results deal with oriented forests. We provide a linear-time algorithm to compute the metric dimension of an oriented forest and a linear-time algorithm that, given a forest F, computes an orientation D - with smallest metric dimension (i.e. such that MD → (D -) = BOMD (F) ) and an orientation D + with largest metric dimension (i.e. such that MD → (D +) = WOMD (F) ). [ABSTRACT FROM AUTHOR]

An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró et al. (Discrete Mathematics 100:267–279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for S d -graphs and T-graphs, where S d is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of S d -graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of S d -graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper S d - and T-graphs. [ABSTRACT FROM AUTHOR]

In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Maxd-Clique and Maxd-Club: A d-clique in a graph G=(V,E) is a subset S⊆V of vertices such that for every pair of vertices u,v∈S, the distance between u and v is at most d in G. A d-club in a graph G=(V,E) is a subset S′⊆V of vertices that induces a subgraph of G of diameter at most d. Given a graph G with n vertices, the goal of Maxd-Clique (Maxd-Club, resp.) is to find a d-clique (d-club, resp.) of maximum cardinality in G. Since Max 1-Clique and Max 1-Club are identical to Max Clique, the inapproximabilty for Max Clique shown by Zuckerman in 2007 is transferred to them. Namely, Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n1-ε for any ε>0 unless P=NP. Also, in 2002, Marinc˘ek and Mohar showed that it is NP-hard to approximate Maxd-Club to within a factor of n1/3-ε for any ε>0 and any fixed d≥2. In this paper, we strengthen the hardness result; we prove that, for any ε>0 and any fixed d≥2, it is NP-hard to approximate Maxd-Club to within a factor of n1/2-ε. Then, we design a polynomial-time algorithm which achieves an optimal approximation ratio of O(n1/2) for any integer d≥2. By using the similar ideas, we show the O(n1/2)-approximation algorithm for Maxd-Clique for any d≥2. This is the best possible in polynomial time unless P=NP, as we can prove the Ω(n1/2-ε)-inapproximability. [ABSTRACT FROM AUTHOR]

A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the input. In particular, we consider parameterizations where the parameter is (instead of the solution size), the distance to a class of graphs where the problem is polynomial time solvable, and sometimes smaller than the solution size. Here, by distance to a class of graphs, we mean the minimum number of vertices whose removal results in a graph in the class. Such a set of vertices is also called the ‘deletion set’. In this paper, we show thatFVS is fixed-parameter tractable by an O(2knO(1)) time algorithm, but is unlikely to have polynomial kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper. We also show that an algorithm with running time O((2-ϵ)knO(1)) is not possible unless SETH fails.When parameterized by k, the number of vertices, whose deletion results in a split graph, we give an O(3.148knO(1)) time algorithm.When parameterized by k, the number of vertices whose deletion results in a cluster graph (a disjoint union of cliques), we give an O(5knO(1)) algorithm. Regarding kernelization results, we show thatWhen parameterized by k, the number of vertices, whose deletion results in a pseudo-forest, FVS has an O(k7) vertices kernel improving from the previously known O(k10) bound.When parameterized by the number k of vertices, whose deletion results in a mock-d-forest, we give a kernel with O(k3d+3) vertices. We also prove a lower bound of Ω(kd+2) size (under complexity theoretic assumptions). Mock-forest is a graph where each vertex is contained in at most one cycle. Mock-d-forest for a constant d is a mock-forest where each component has at most d cycles. [ABSTRACT FROM AUTHOR]

Given a network represented by a graph G=(V,E), we consider a dynamical process of influence diffusion in G that evolves as follows: Initially only the nodes of a given S⊆V are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The question is to determine a small subset of nodes S (a target set) that can influence the whole network. This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known that the above optimization problem is hard to approximate within a factor of 2log1-ϵ|V|, for any ϵ>0. In this paper, we present a fast and surprisingly simple algorithm that exhibits the following features: (1) when applied to trees, cycles, or complete graphs, it always produces an optimal solution (i.e, a minimum size target set); (2) when applied to arbitrary networks, it always produces a solution of cardinality which improves on previously known upper bounds; (3) when applied to real-life networks, it always produces solutions that substantially outperform the ones obtained by previously published algorithms (for which no proof of optimality or performance guarantee is known in any class of graphs). [ABSTRACT FROM AUTHOR]

The Maximum Happy Vertices (MHV) problem and the Maximum Happy Edges (MHE) problem are two fundamental problems arising in the study of the homophyly phenomenon in large scale networks. Both of these two problems are NP-hard. Interestingly, the MHE problem is a natural generalization of Multiway Uncut, the complement of the classic Multiway Cut problem. In this paper, we present new approximation algorithms for MHV and MHE based on randomized LP-rounding technique and non-uniform approach. Specifically, we show that MHV can be approximated within 1/Δ+1/g(Δ) , where Δ is the maximum vertex degree and g(Δ) = ( √ Δ + √ Δ + 1)2Δ, and MHE can be approximated within 1 2 + √ 2 4 f (k) ≥ 0.8535, where f (k) ≥ 1 is a function of the color number k. These results improve over the previous approximation ratios for MHV, MHE as well as Multiway Uncut in the literature. [ABSTRACT FROM AUTHOR]

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T , w , d min , d max) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d min ≤ d max such that G has an edge between two vertices u , v ∈ V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [ d min , d max ] . The tree T is also called a witness tree of the PCG G. How to recognize PCGs is a wide-open problem in the literature. This paper gives a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs. [ABSTRACT FROM AUTHOR]

Let $${\mathcal {F}}$$ be a family of graphs. Given an n-vertex input graph G and a positive integer k, testing whether G has a vertex subset S of size at most k, such that $$G-S$$ belongs to $${\mathcal {F}}$$ , is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when $${\mathcal {F}}$$ is either the family of forests of cacti or the family of forests of odd-cacti. A graph H is called a forest of cacti if every pair of cycles in H intersect on at most one vertex. Furthermore, a forest of cacti H is called a forest of odd cacti, if every cycle of H is of odd length. Let us denote by $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ , the families of forests of cacti and forests of odd cacti, respectively. The vertex deletion problems corresponding to $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with worst case run time $$12^k n^{\mathcal {O}(1)}$$ for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them. [ABSTRACT FROM AUTHOR]

Recent papers on approximation algorithms for the traveling salesman problem (TSP) have given a new variant of the well-known Christofides' algorithm for the TSP, called the Best-of-Many Christofides' algorithm. The algorithm involves sampling a spanning tree from the solution to the standard LP relaxation of the TSP, subject to the condition that each edge is sampled with probability at most its value in the LP relaxation. One then runs Christofides' algorithm on the tree by computing a minimum-cost matching on the odd-degree vertices in the tree, and shortcutting a traversal of the resulting Eulerian graph to a tour. In this paper we perform an experimental evaluation of the Best-of-Many Christofides' algorithm to see if there are empirical reasons to believe its performance is better than that of Christofides' algorithm. Furthermore, several different sampling schemes have been proposed; we implement several different schemes to determine which ones might be the most promising for obtaining improved performance guarantees over that of Christofides' algorithm. In our experiments, all of the implemented methods perform significantly better than Christofides' algorithm; an algorithm that samples from a maximum entropy distribution over spanning trees seems to be particularly good, though there are others that perform almost as well. [ABSTRACT FROM AUTHOR]

Abstract  In a finite undirected graph, an apple consists of a chordless cycle of length at least 4, and an additional vertex which is not in the cycle and sees exactly one of the cycle vertices. A graph is apple-free if it contains no induced subgraph isomorphic to an apple. Apple-free graphs are a common generalization of chordal graphs, claw-free graphs and cographs and occur in various papers. The Maximum Weight Independent Set (MWS) problem is efficiently solvable on chordal graphs, on cographs as well as on claw-free graphs. In this paper, we obtain partial results on some subclasses of apple-free graphs where our results show that the MWS problem is solvable in polynomial time. The main tool is a combination of clique separators with modular decomposition. Our algorithms are robust in the sense that there is no need to recognize whether the input graph is in the given graph class; the algorithm either solves the MWS problem correctly or detects that the input graph is not in the given class. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we study the problems of enumerating cuts of a graph by non-decreasing weights. There are four problems, depending on whether the graph is directed or undirected, and on whether we consider all cuts of the graph or only s-t cuts for a given pair of vertices s,t. Efficient algorithms for these problems with delay between two successive outputs have been known since 1992, due to Vazirani and Yannakakis. In this paper, improved algorithms are presented. The delays of the presented algorithms are O(nmlog (n 2/m)). Vazirani and Yannakakis’s algorithms have been used as basic subroutines in the solutions of many problems. Therefore, our improvement immediately reduces the running time of these solutions. For example, for the minimum k-cut problem, the upper bound is immediately reduced by a factor of for k=3,4,5,6. [ABSTRACT FROM AUTHOR]

Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for graphs of bounded bandwidth. This fact rules out the tractability of parameterizations by most well-studied structural parameters as most of them generalize bandwidth. In this paper, we study the parameterization by modular-width, which is not comparable with bandwidth. We show that the problem parameterized by modular-width is fixed-parameter tractable under all previously studied rules TAR , TJ , and TS . The result under TAR resolves an open problem posed by Bonsma (J Graph Theory 83(2):164–195, 2016). [ABSTRACT FROM AUTHOR]

Abstract. Symmetric graph drawing enables a clear understanding of the structure of the graph. Previous work on symmetric graph drawing has focused on two dimensions. Symmetry in three dimensions is much richer than that of two dimensions. This is the first paper to extend symmetric graph drawing into three dimensions. More specifically, the paper investigates the problem of drawing trees symmetrically in three dimensions. First, we suggest a model for drawing trees symmetrically in three dimensions. Based on this model, we present a linear time algorithm for finding the maximum number of three-dimensional symmetries in trees. We also present a three-dimensional symmetric drawing algorithm for trees. [ABSTRACT FROM AUTHOR]

Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying link behind all these orders has been shown that links them to well-known graph decompositions into parts that have a prescribed vertex-connectivity. Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edge-connectivity. In this paper, we establish such a concept named edge-orders and show how to compute (1, 1)-edge-orders of 2-edge-connected graphs as well as (2, 1)-edge-orders of 3-edge-connected graphs in linear time, respectively. While the former can be seen as the edge-variants of st-numberings, the latter are the edge-variants of Mondshein sequences and non-separating ear decompositions. The methods that we use for obtaining such edge-orders differ considerably in almost all details from the ones used for their vertex-counterparts, as different graph-theoretic constructions are used in the inductive proof and standard reductions from edge- to vertex-connectivity are bound to fail. As a first application, we consider the famous Edge-Independent Spanning Tree Conjecture, which asserts that every k-edge-connected graph contains k rooted spanning trees that are pairwise edge-independent. We illustrate the impact of the above edge-orders by deducing algorithms that construct 2- and 3-edge independent spanning trees of 2- and 3-edge-connected graphs, the latter of which improves the best known running time from O (n 2) to linear time. [ABSTRACT FROM AUTHOR]

A directed multigraph is said vulnerable if it can generate Braess paradox in traffic networks. In this paper, we give a graph–theoretic characterisation of vulnerable directed multigraphs. Analogous results appeared in the literature only for undirected multigraphs and for a specific family of directed multigraphs. The proof of our characterisation provides the first polynomial time algorithm that checks if a general directed multigraph is vulnerable in O (| V | · | E | 2) . Our algorithm also contributes to the directed subgraph homeomorphism problem without node mapping, by providing another pattern graph for which a polynomial time algorithm exists. [ABSTRACT FROM AUTHOR]

Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low independence. A series of papers, beginning with work by Luby (1988), showed that in many cases these techniques can be combined to give deterministic parallel (NC) algorithms for a variety of combinatorial optimization problems, with low time- and processor-complexity. We extend and generalize a technique of Luby for efficiently handling bilinear objective functions. One noteworthy application is an NC algorithm for maximal independent set. On a graph G with m edges and n vertices, this takes O~(log2n) time and (m+n)no(1) processors, nearly matching the best randomized parallel algorithms. Other applications include reduced processor counts for algorithms of Berger (SIAM J Comput 26:1188-1207, 1997) for maximum acyclic subgraph and Gale-Berlekamp switching games. This bilinear factorization also gives better algorithms for problems involving discrepancy. An important application of this is to automata-fooling probability spaces, which are the basis of a notable derandomization technique of Sivakumar (In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp 619-626, 2002). Our method leads to large reduction in processor complexity for a number of derandomization algorithms based on automata-fooling, including set discrepancy and the Johnson-Lindenstrauss Lemma. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph G=(V,E) with n=|V| and m=|E|, and an integer value k≥1, there is an algorithm that computes in O(2knlog2n) time for any set F of size at most k the strongly connected components of the graph G\F. The running time of our algorithm is almost optimal since the time for outputting the SCCs of G\F is at least Ω(n). The algorithm uses a data structure that is computed in a preprocessing phase in polynomial time and is of size O(2kn2). Our result is obtained using a new observation on the relation between strongly connected components (SCCs) and reachability. More specifically, one of the main building blocks in our result is a restricted variant of the problem in which we only compute strongly connected components that intersect a certain path. Restricting our attention to a path allows us to implicitly compute reachability between the path vertices and the rest of the graph in time that depends logarithmically rather than linearly in the size of the path. This new observation alone, however, is not enough, since we need to find an efficient way to represent the strongly connected components using paths. For this purpose we use a mixture of old and classical techniques such as the heavy path decomposition of Sleator and Tarjan (J Comput Syst Sci 26:362-391, 1983) and the classical Depth-First-Search algorithm. Although, these are by now standard techniques, we are not aware of any usage of them in the context of dynamic maintenance of SCCs. Therefore, we expect that our new insights and mixture of new and old techniques will be of independent interest. [ABSTRACT FROM AUTHOR]

The all scores matrix of a grid graph is a matrix containing the optimal scores of paths from every vertex on the first row of the graph to every vertex on its last row. This matrix is commonly used to solve diverse string comparison problems. All scores matrices have the Monge property, and this was exploited by previous works that used all scores matrices for solving various problems. In this paper, we study an extension of grid graphs that contain an additional set of edges, called bridges. Our main result is to show several properties of the all scores matrices of such graphs. We also apply these properties to obtain an O(r(nm+n2)) time algorithm for constructing the all scores matrix of an m×n grid graph with r bridges and bounded integer weights. [ABSTRACT FROM AUTHOR]

Given a fixed graph $$H$$ , the $$H$$ - Free Edge Deletion (resp., Completion, Editing) problem asks whether it is possible to delete from (resp., add to, delete from or add to) the input graph at most $$k$$ edges so that the resulting graph is $$H$$ -free, i.e., contains no induced subgraph isomorphic to $$H$$ . These $$H$$ -free edge modification problems are well known to be fixed-parameter tractable for every fixed $$H$$ . In this paper we study the incompressibility, i.e., nonexistence of polynomial kernels, for these $$H$$ -free edge modification problems in terms of the structure of $$H$$ , and completely characterize their nonexistence for $$H$$ being paths, cycles or 3-connected graphs. We also give a sufficient condition for the nonexistence of polynomial kernels for $${\mathcal {F}}$$ - Free Edge Deletion problems, where $${\mathcal {F}}$$ is a finite set of forbidden induced subgraphs. As an effective tool, we have introduced an incompressible constraint satisfiability problem Propagational- $$f$$ Satisfiability to express common propagational behaviors of events, and we expect the problem to be useful in studying the nonexistence of polynomial kernels in general. [ABSTRACT FROM AUTHOR]

Given an undirected graph on a node set V and positive integers k and m, a k-connected m-dominating set ((k, m)-CDS) is defined as a subset S of V such that each node in V\S has at least m neighbors in S, and a k-connected subgraph is induced by S. The weighted (k, m)-CDS problem is to find a minimum weight (k, m)-CDS in a given node-weighted graph. The problem is called the unweighted (k, m)-CDS problem if the objective is to minimize the cardinality of a (k, m)-CDS. These problems have been actively studied for unit disk graphs, motivated by the application of constructing a virtual backbone in a wireless ad hoc network. In this paper, we consider the case in which k≤m, and we present a simple O(k5k)-approximation algorithm for the unweighted (k, m)-CDS problem, and a primal-dual O(k2logk)-approximation algorithm for the weighted (k, m)-CDS problem. [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.

In this paper we consider a problem that arises from a strategic issue in the stable matching model (with complete preference lists) from the viewpoint of exact-exponential time algorithms. Specifically, we study the STABLE EXTENSION OF PARTIAL MATCHING (SEOPM) problem, where the input consists of the complete preference lists of men, and a partial matching. The objective is to find (if one exists) a set of preference lists of women, such that the men-optimal Gale-Shapley algorithm outputs a perfect matching that contains the given partial matching. Kobayashi and Matsui (Algorithmica 58:151-169, 2010) proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time 2O(n), where n denotes the number of men/women. We complement our algorithmic finding by showing that unless Exponential Time Hypothesis (ETH) fails, our algorithm is asymptotically optimal. That is, unless ETH fails, there is no algorithm for SEOPM running in time 2o(n). Our algorithm is a non-trivial combination of a parameterized algorithm for SUBGRAPH ISOMORPHISM, a relationship between stable matching and finding an out-branching in an appropriate graph and enumerating all possible non-isomorphic out-branchings. Our results cover both the cases when the preference lists are strict and complete, and when they are strict but possibly incomplete. [ABSTRACT FROM AUTHOR]

The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results:We show that an algorithm by Crowston et al. (Algorithmica 72(3):734-757, 2015) for (SIGNED) MAX-CUT ABOVE EDWARDS−ERDőS BOUND can be implemented so as to run in linear time8k·O(m); this significantly improves the previous analysis with run time 8k·O(n4).We give an asymptotically optimal kernel for (SIGNED) MAX-CUT ABOVE EDWARDS−ERDőS BOUND with O(k) vertices, improving a kernel with O(k3) vertices by Crowston et al. (Theor Comput Sci 513:53-64, 2013).We improve all known kernels for parameterizations above strongly λ-extendible properties (a generalization of the MAX-CUT results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics, Guwahati, 2013) from O(k3) vertices to O(k) vertices.Therefore, MAX ACYCLIC SUBDIGRAPH parameterized above Poljak-Turzík bound admits a kernel with O(k) vertices and can be solved in 2O(k)·nO(1) time; this answers an open question by Crowston et al. (Proceedings of FSTTCS 2012, Leibniz international proceedings in informatics, Hyderabad, 2012). All presented kernels can be computed in time O(km). [ABSTRACT FROM AUTHOR]

In the TOKEN SWAPPING problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that TOKEN SWAPPING is W[1]-hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k)no(k/logk) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial nO(k)-time algorithm. We also consider two generalizations of the TOKEN SWAPPING, namely COLORED TOKEN SWAPPING (where the tokens have colors and tokens of the same color are indistinguishable), and SUBSET TOKEN SWAPPING (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, SUBSET TOKEN SWAPPING, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases. [ABSTRACT FROM AUTHOR]

Björklund and Husfeldt developed a randomized polynomial time algorithm to solve the shortest two disjoint paths problem. Their algorithm is based on computation of permanents modulo 4 and the isolation lemma. In this paper, we consider the following generalization of the shortest two disjoint paths problem, and develop a similar algebraic algorithm. The shortest perfect (A+B)-path packing problem is: given an undirected graph G and two disjoint node subsets A, B with even cardinalities, find shortest |A|/2+|B|/2 disjoint paths whose ends are both in A or both in B. Besides its NP-hardness, we prove that this problem can be solved in randomized polynomial time if |A|+|B| is fixed. Our algorithm basically follows the framework of Björklund and Husfeldt but uses a new technique: computation of hafnian modulo 2k combined with Gallai’s reduction from T-paths to matchings. We also generalize our technique for solving other path packing problems, and discuss its limitation. [ABSTRACT FROM AUTHOR]

A tree-child network is a phylogenetic network with the property that each non-leaf vertex is the parent of a tree vertex or a leaf. In this paper, we show that a tree-child network on taxa (leaf) set X with an outgroup and a positive real-valued weighting of its edges is essentially determined by the multi-set of all path-length distances between elements in X provided, for each reticulation, the edges directed into it have equal weight. Furthermore, we give a polynomial-time algorithm for reconstructing such a network from this inter-taxa distance information. Such constructions are of central importance in evolutionary biology where phylogenetic networks represent the ancestral history of a collection of present-day taxa. [ABSTRACT FROM AUTHOR]

We study the max-min fair allocation problem in which a set of m indivisible items are to be distributed among n agents such that the minimum utility among all agents is maximized. In the restricted setting, the utility of each item j on agent i is either 0 or some non-negative weight wj. For this setting, Asadpour et al. (ACM Trans Algorithms 8(3):24, 2012) showed that a certain configuration-LP can be used to estimate the optimal value to within a factor of 4+δ, for any δ>0, which was recently extended by Annamalai et al. (in: Indyk (ed) Proceedings of the twenty-sixth annual ACMSIAM symposium on discrete algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015) to give a polynomial-time 13-approximation algorithm for the problem. For hardness results, Bezáková and Dani (SIGecom Exch 5(3):11-18, 2005) showed that it is NP-hard to approximate the problem within any ratio smaller than 2. In this paper we consider the (1,ϵ)-restricted max-min fair allocation problem in which each item j is either heavy (wj=1) or light (wj=ϵ), for some parameter ϵ∈(0,1). We show that the (1,ϵ)-restricted case is also NP-hard to approximate within any ratio smaller than 2. Using the configuration-LP, we are able to estimate the optimal value of the problem to within a factor of 3+δ, for any δ>0. Extending this idea, we also obtain a quasi-polynomial time (3+4ϵ)-approximation algorithm and a polynomial time 9-approximation algorithm. Moreover, we show that as ϵ tends to 0, the approximation ratio of our polynomial-time algorithm approaches 3+22≈5.83. [ABSTRACT FROM AUTHOR]

The problem MaxW-Light (MaxW-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-Light is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MaxW-Heavy can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MaxW-Light, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54-87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results. [ABSTRACT FROM AUTHOR]

The notion of clique-width for graphs offers many research topics and has received considerable attention in the past decade. A graph has clique-width k if it can be represented as an algebraic expression on k labels associated with its vertices. Many computationally hard problems can be solved in polynomial time for graphs of bounded clique-width. Interestingly also, many graph families have bounded clique-width. In this paper, we consider the problem of preprocessing a graph of size n and clique-width k to build space-efficient data structures that support basic graph navigation queries. First, by way of a counting argument, which is of interest in its own right, we prove the space requirement of any representation is Ω(kn). Then we present a navigation oracle which answers adjacency query in constant time and neighborhood queries in constant time per neighbor. This oracle uses O(kn) space (i.e., O(kn) bits). We also present a degree query which reports the degree of each given vertex in O(klog∗(n)) time using O(knlog∗(n)) bits. [ABSTRACT FROM AUTHOR]

This paper is devoted to new results about the scaffolding problem, an integral problem of genome inference in bioinformatics. The problem consists in finding a collection of disjoint cycles and paths covering a particular graph called the “scaffold graph”. We examine the difficulty and the approximability of the scaffolding problem in special classes of graphs, either close to trees, or very dense. We propose negative and positive results, exploring the frontier between difficulty and tractability of computing and/or approximating a solution to the problem. Also, we explore a new direction through related problems consisting in finding a family of edges having a strong effect on solution weight. [ABSTRACT FROM AUTHOR]

A simultaneous embedding (with fixed edges) of two graphs G1 and G2 with common graph G=G1∩G2 is a pair of planar drawings of G1 and G2 that coincide on G. It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph G∪=G1∪G2, (2) most separating pairs of G∪, and (3) connected components of G that are biconnected but not a cycle. Second, we give an O(n3)-time algorithm solving Sefe for instances with the following restriction. Let u be a pole of a P-node μ in the SPQR-tree of a block of G1 or G2. Then at most three virtual edges of μ may contain common edges incident to u. All algorithms extend to the sunflower case, i.e., to the case of more than two graphs pairwise intersecting in the same common graph. [ABSTRACT FROM AUTHOR]

In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover (vc) and modular width (mw). We prove that for any graph, the number of its minimal separators is O∗(3vc) and O∗(1.6181mw), and the number of potential maximal cliques is O∗(4vc) and O∗(1.7347mw), and these objects can be listed within the same running times (The O∗ notation suppresses polynomial factors in the size of the input). Combined with known applications of potential maximal cliques, we deduce that a large family of problems, e.g., Treewidth, Minimum Fill-in, Longest Induced Path, Feedback vertex set and many others, can be solved in time O∗(4vc) or O∗(1.7347mw). With slightly different techniques, we prove that the Treedepth problem can be also solved in single-exponential time, for both parameters. [ABSTRACT FROM AUTHOR]

In the k-center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum distance between an element of V and its assigned center. One of the most general variants is the capacitatedα-fault-tolerant k-center, where centers have a limit on the number of assigned elements, and, if any α centers fail, there is a reassignment from V to non-faulty centers. In this paper, we present a new approach to tackle fault tolerance, by selecting and pre-opening a set of backup centers, then solving the obtained residual instance. For the {0,L}-capacitated case, we give approximations with factor 6 for the basic problem, and 7 for the so called conservative variant, when only clients whose centers failed may be reassigned. Our algorithms improve on the best previously known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming α is constant, our method leads to the first approximations for this case. We also derive approximations for the capacitated fault-tolerant k-supplier problem. [ABSTRACT FROM AUTHOR]

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph $$G= (A\, \dot{\cup }\, P, E)$$ with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between $$\textsf {NP}$$ -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $$u_{\max }$$ as basis, and we prove that this dependence is necessary unless $$\textsf {FPT}= \textsf {W}[1]$$ . The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee $$u_{\max }+1$$ , which is asymptotically best possible unless $$\textsf {P}= \textsf {NP}$$ . Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas. [ABSTRACT FROM AUTHOR]

For a set $$\mathcal {H}$$ of graphs, the $$\mathcal {H}$$ - free Edge Deletion problem is to decide whether there exist at most k edges in the input graph, for some $$k\in \mathbb {N}$$ , whose deletion results in a graph without an induced copy of any of the graphs in $$\mathcal {H}$$ . The problem is known to be fixed-parameter tractable if $$\mathcal {H}$$ is of finite cardinality. In this paper, we present a polynomial kernel for this problem for any fixed finite set $$\mathcal {H}$$ of connected graphs for the case where the input graphs are of bounded degree. We use a single kernelization rule which deletes vertices 'far away' from the induced copies of every $$H\in \mathcal {H}$$ in the input graph. With a slightly modified kernelization rule, we obtain polynomial kernels for $$\mathcal {H}$$ - free Edge Deletion under the following three settings: where $$s>1$$ and $$t>2$$ are any fixed integers. Our result provides the first polynomial kernels for Claw-free Edge Deletion and Line Edge Deletion for $$K_t$$ -free input graphs which are known to be NP-complete even for $$K_4$$ -free graphs. [ABSTRACT FROM AUTHOR]

Fan-planar graphs were recently introduced as a generalization of 1- planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed more than once, is crossed by a bundle of two or more edges incident to a common vertex. A graph is outer-fan-planar if it has a fan-planar embedding in which every vertex is on the outer face. If, in addition, the insertion of an edge destroys its outer-fan-planarity, then it is maximal outer-fan-planar. In this paper, we present a linear-time algorithm to test whether a given graph is maximal outer-fan-planar. The algorithm can also be employed to produce an outer-fan-planar embedding, if one exists. On the negative side, we show that testing fan-planarity of a graph is NP-complete, for the case where the rotation system (i.e., the cyclic order of the edges around each vertex) is given. [ABSTRACT FROM AUTHOR]

In a book embedding, the vertices of a graph are placed on the 'spine' of a book and the edges are assigned to 'pages', so that edges on the same page do not cross. In this paper, we prove that every 1-planar graph (that is, a graph that can be drawn on the plane such that no edge is crossed more than once) admits an embedding in a book with constant number of pages. To the best of our knowledge, the best non-trivial previous upper-bound is $$O(\sqrt{n})$$ , where n is the number of vertices of the graph. [ABSTRACT FROM AUTHOR]

Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighbor instances, that is, instances with one local modification? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems, most notably, graph theory's core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, colorability and vertex cover. For example, we show that it is NP -hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P . We observe that vertex cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For vertex cover, we show that recognizing β -vertex-critical graphs is complete for Θ 2 p (parallel access to NP ), obtaining the first completeness result for a criticality problem for this class. [ABSTRACT FROM AUTHOR]

We study the problem of dynamically updating all-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes. In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO's widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford. [ABSTRACT FROM AUTHOR]

In this paper we study the prevalent problem of graph partitioning by analyzing the diffusion-based partitioning heuristic Bubble-FOS/C, a key component of a practical successful graph partitioner (Meyerhenke et al. in J. Parallel Distrib. Comput. 69(9):750-761, ). We begin by studying the disturbed diffusion scheme FOS/C, which computes the similarity measure used in Bubble-FOS/C and is therefore the most crucial component. By relating FOS/C to random walks, we obtain precise characterizations of the behavior of FOS/C on tori and hypercubes. Besides leading to new knowledge on FOS/C (and therefore also on Bubble-FOS/C), these characterizations have been recently used for the analysis of load balancing algorithms (Berenbrink et al. in Proceedings of the 22nd Annual Symposium on Discrete Algorithms, pp. 429-439, ). We then regard Bubble-FOS/C, which has been shown in previous experiments to produce solutions with good partition shapes and other favorable properties. In this paper we prove that it computes a relaxed solution to an edge cut minimizing binary quadratic program (BQP). This result provides the first substantial theoretical insight why Bubble-FOS/C yields good experimental results in terms of graph partitioning metrics. Moreover, we show that in bisections computed by Bubble-FOS/C, at least one of the two parts is connected. Using the aforementioned relation between FOS/C and random walks, we prove that in vertex-transitive graphs both parts must be connected components. [ABSTRACT FROM AUTHOR]