Search

We show that every graph with pathwidth strictly less than a that contains no path on 2 b vertices as a subgraph has treedepth at most 10ab. The bound is best possible up to a constant factor. [ABSTRACT FROM AUTHOR]

The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. A widely-studied special case are edge-colored graphs, where a compatible walk is forbidden to take two edges of the same color in a row. We initiate the study of fundamental problems on finding paths, cycles and walks in forbidden-transition graphs from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth for finding a compatible Hamiltonian cycle in the edge-colored graph setting. [ABSTRACT FROM AUTHOR]

The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph G. Here, a set S ⊆ V (G) is resolving if no two distinct vertices of G have the same distance vector to S. The complexity of Metric Dimension in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that Metric Dimension is NP-hard in graphs of treewidth 24 . [ABSTRACT FROM AUTHOR]

Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth. These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates the run time of existing algorithms in practice. We introduce p-linear colorings as an alternative to the commonly used p-centered colorings. They can be efficiently computed in bounded expansion classes and use at most as many colors as p-centered colorings. Although a set of k < p colors from a p-centered coloring induces a subgraph of treedepth at most k, the same number of colors from a p-linear coloring may induce subgraphs of larger treedepth. We establish a polynomial upper bound on the treedepth in general graphs, and give tighter bounds in trees and interval graphs via constructive coloring algorithms. We also give a co-NP-completeness reduction for recognizing p-linear colorings and discuss ways to overcome this limitation in practice. [ABSTRACT FROM AUTHOR]

We study the Independent Feedback Vertex Set problem — a variant of the classic Feedback Vertex Set problem where, given a graph G and an integer k, the problem is to decide whether there exists a vertex set S ⊆ V (G) such that G ∖ S is a forest and S is an independent set of size at most k. We present an O ∗ ((1 + φ 2) k) -time FPT algorithm for this problem, where φ < 1.619 is the golden ratio, improving the previous fastest O ∗ (4.148 1 k) -time algorithm given by Agrawal et al. (2016). The exponential factor in our time complexity bound matches the fastest deterministic FPT algorithm for the classic Feedback Vertex Set problem. On the technical side, the main novelty is a refined measure of an input instance in a branching process, that allows for a simpler and more concise description and analysis of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: Skew Multicut and Directed Feedback Arc Set. In our generalization, we assign colors 1 , 2 , ... , ℓ to some edges and give separate budgets k 1 , k 2 , ... , k ℓ for colors 1 , 2 , ... , ℓ . For every color i ∈ { 1 , ... , ℓ } , let E i be the set of edges of color i. The solution C for the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements (i.e., be a cut, a skew multicut, or a directed feedback arc set, respectively), but also needs to satisfy that | C ∩ E i | ≤ k i for every i ∈ { 1 , ... , ℓ } . Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for ℓ = 2 . We propose FPT algorithms parameterized by k = k 1 + ⋯ + k ℓ for all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducing k as usual, by but elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to the Skew Multicut and Directed Feedback Arc Set problems. Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and the Chain ℓ -SAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of "maximally pushed" solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability. [ABSTRACT FROM AUTHOR]

The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k -Path admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k O (1) ? We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and K 3 , t -minor-free graphs. Moreover, we show that k -Path even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path, has a separation that can safely be reduced after communication with the oracle. [ABSTRACT FROM AUTHOR]

Given an edge-weighted graph G with a set Q of k terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the size of minimum cut between any partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph G being either an arbitrary graph or coming from a specific graph class. We show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with k terminals that require 2 k - 2 edges in any mimicking network. This nearly matches an upper bound of O (k 2 2 k) of Krauthgamer and Rika (in: Khanna (ed) Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, 2013) and is in sharp contrast with the upper bounds of O (k 2) and O (k 4) under the assumption that all terminals lie on a single face (Goranci et al., in: Pruhs and Sohler (eds) 25th Annual European symposium on algorithms (ESA 2017), 2017, arXiv:1702.01136; Krauthgamer and Rika in Refined vertex sparsifiers of planar graphs, 2017, arXiv:1702.05951). As a side result we show a tight example for double-exponential upper bounds given by Hagerup et al. (J Comput Syst Sci 57(3):366–375, 1998), Khan and Raghavendra (Inf Process Lett 114(7):365–371, 2014), and Chambers and Eppstein (J Gr Algorithms Appl 17(3):201–220, 2013). [ABSTRACT FROM AUTHOR]

We show that a problem of deleting a minimum number of vertices from a graph to obtain a graph embeddable on a surface of a given Euler genus is solvable in time 2 C g · k 2 log k n O (1) , where k is the size of the deletion set, C g is a constant depending on the Euler genus g of the target surface, and n is the size of the input graph. On the way to this result, we develop an algorithm solving the problem in question in time 2 O ((t + g) log (t + g)) n given a tree decomposition of the input graph of width t. The results generalize previous algorithms for the surface being a sphere by Marx and Schlotter (Algorithmica 62(3–4):807–822, 2012. 10.1007/s00453-010-9484-z), Kawarabayashi (in: 50th annual IEEE symposium on foundations of computer science, FOCS 2009, IEEE Computer Society, pp 639–648, 2009. 10.1109/FOCS.2009.45) and Jansen et al. (in: Chekuri (ed) 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, SIAM, pp 1802–1811, 2014. 10.1137/1.9781611973402.130). [ABSTRACT FROM AUTHOR]

In the EDGE BIPARTIZATION problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. Guo et al. (J Comput Syst Sci 72(8):1386-1396, 2006) proposed an algorithm solving this problem in time O(2k·m2); today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for EDGE BIPARTIZATION that works in time O(1.977k·nm), which is the first algorithm with the running time dependence on the parameter better than 2k. To this end, we combine the general iterative compression strategy of Guo et al.  (2006), the technique proposed by Wahlström (in: Proceedings of SODA'14, SIAM, 2014) of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree. [ABSTRACT FROM AUTHOR]

In algorithmic graph theory, a classic open question is to determine the complexity of the MAXIMUM INDEPENDENT SET problem on Pt-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t≤5 (Lokshtanov et al., in: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5-7, 2014, pp 570-581, 2014), and an algorithm for t=6 announced recently (Grzesik et al. in Polynomial-time algorithm for maximum weight independent set on P6-free graphs. CoRR, arXiv:1707.05491, 2017). Here we study the existence of subexponential-time algorithms for the problem: we show that for any t≥1, there is an algorithm for MAXIMUM INDEPENDENT SET on Pt-free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in 2O(tnlogn) time on Pt-free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. SCATTERED SET is the generalization of MAXIMUM INDEPENDENT SET where the vertices of the solution are required to be at distance at least d from each other. We give a complete characterization of those graphs H for which d-SCATTERED SET on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges):If every component of H is a path, then d-SCATTERED SET on H-free graphs with n vertices and m edges can be solved in time 2O(|V(H)|n+mlog(n+m)), even if d is part of the input.Otherwise, assuming the Exponential-Time Hypothesis (ETH), there is no 2o(n+m)-time algorithm for d-SCATTERED SET for any fixed d≥3 on H-free graphs with n-vertices and m-edges. [ABSTRACT FROM AUTHOR]

A graph is called {claw,diamond}-free if it contains neither a claw (a K ) nor a diamond (a K with an edge removed) as an induced subgraph. Equivalently, {claw,diamond}-free graphs are characterized as line graphs of triangle-free graphs, or as linear dominoes (graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique). We consider the parameterized complexity of the {claw,diamond}-free Edge Deletion problem, where given a graph G and a parameter k, the question is whether one can remove at most k edges from G to obtain a {claw,diamond}-free graph. Our main result is that this problem admits a polynomial kernel. We complement this result by proving that, even on instances with maximum degree 6, the problem is NP-complete and cannot be solved in time $2^{o(k)}\cdot |V(G)|^{\mathcal {O}(1)}$ unless the Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

In the paper entitled " I Finding optimal triangulations parameterized by edge clique cover i ", Tuukka Korhonen presents algorithms for computing, among others, treewidth and minimum fill-in, parameterized by the edge clique cover number. They present parameterized algorithms for solving Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal, among other problems, and their algorithms do not assume a given modulator. In " I Structural parameterizations with modulator oblivion i ", Ashwin Jacob, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot consider the structural parameterization of the vertex-deletion distance to chordal graphs. [Extracted from the article]

In the family of clustering problems we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques). Hüffner et al. (Theory Comput. Syst. 47(1), 196-217, ) initiated the parameterized study of Cluster Vertex Deletion, where the allowed modification is vertex deletion, and presented an elegant $\mathcal {O}\left (\min (2^{k} k^{6} \log k + n^{3}, 2^{k} km\sqrt {n} \log n)\right )$-time fixed-parameter algorithm, parameterized by the solution size. In the last 5 years, this algorithm remained the fastest known algorithm for Cluster Vertex Deletion and, thanks to its simplicity, became one of the textbook examples of an application of the iterative compression principle. In our work we break the 2-barrier for Cluster Vertex Deletion and present an $\mathcal {O}(1.9102^{k} (n+m))$-time branching algorithm. We achieve this improvement by a number of structural observations which we incorporate into the algorithm's branching steps. [ABSTRACT FROM AUTHOR]