Search

We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class G there exists a constant k such that no member of G contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ G contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput., 44 (2015), pp. 54-87] the latter entails the existence of polynomial-time algorithms for MAXIMUM WEIGHT INDEPENDENT SET, FEEDBACK VERTEX SET and many other problems, when restricted to an input graph from G. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators). [ABSTRACT FROM AUTHOR]

A bramble in an undirected graph G is a family of connected subgraphs of G such that for every two subgraphs H1 and H2 in the bramble either V (H1) \ V (H2) 6=; or there is an edge of G with one endpoint in V (H1) and the second endpoint in V (H2). The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble. Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph G equals one plus the treewidth of G. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree n-vertex expander a bramble of order (n1=2+δ) requires size exponential in (n2δ) for any fixed δ 2 (0; 1 2 ]. On the other hand, the combination of results of Grohe and Marx and Chekuri and Chuzhoy shows that a graph of treewidth k admits a bramble of order e(k1=2) and size e O(k3=2). (e and e O hide polylogarithmic divisors and factors, respectively.). In this note, we first sharpen the second bound by proving that every graph G of treewidth at least k contains a bramble of order e(k1=2) and congestion 2, i.e., every vertex of G is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every δ 2 (0; 1 2 ], every graph G of treewidth at least k contains a bramble of order e(k1=2+δ) and size 2 eO (k2δ). [ABSTRACT FROM AUTHOR]

Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant C such that for all positive integers a, b and a graph G, if the treedepth of G is at least Cab, then the treewidth of G is at least a or G contains a subcubic (i.e., of maximum degree at most 3) tree of treedepth at least b as a subgraph. As a direct corollary, we obtain that every graph of treedepth Omega (k3) either is of treewidth at least k, contains a subdivision of full binary tree of depth k, or contains a path of length 2k. This improves the bound of Omega (k5 log2 k) of Kawarabayashi and Rossman [Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 234--246]. We also show an application of our techniques for approximation algorithms of treedepth: given a graph G of treedepth k and treewidth t, one can in polynomial time compute a treedepth decomposition of G of width scrO (kt log3/2 t). This improves upon a bound of scrO (kt2 log t) stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth d contains a subcubic subtree of treedepth at least d cdot log3((1 + surd 5)/2). [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 PROPER INTERVAL COMPLETION problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of PROPER INTERVAL COMPLETION from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir, and Tarjan [SIAM J. Comput., 28 (1999), pp. 1906-1922], who showed an algorithm for the problem working in O(16k (n+m)) time. In this paper we present an algorithm with running time kO(k2/3) + O(nm(kn + m)), which is the first subexponential parameterized algorithm for PROPER INTERVAL COMPLETION. [ABSTRACT FROM AUTHOR]

We present a number of exponential-time algorithms for problems in sparse matrices and graphs of bounded average degree. First, we obtain a simple algorithm that computes a permanent of an n × n matrix over an arbitrary commutative ring with at most dn non-zero entries using O ⋆ ( 2 ( 1 − 1 / ( 3.55 d ) ) n ) time and ring operations, 1 improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012]. Second, we present a simple algorithm for counting perfect matchings in an n -vertex graph in O ⋆ ( 2 n / 2 ) time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Björklund [SODA 2012], but relies on inclusion–exclusion principle instead of algebraic transformations. Third, we show a combinatorial lemma that bounds the number of “Hamiltonian-like” structures in a graph of bounded average degree. Using this result, we show that 1. a minimum weight Hamiltonian cycle in an n -vertex graph with average degree bounded by d can be found in O ⋆ ( 2 ( 1 − ε d ) n ) time and exponential space for a constant ε d depending only on d ; 2. the number of perfect matchings in an n -vertex graph with average degree bounded by d can be computed in O ⋆ ( 2 ( 1 − ε d ′ ) n / 2 ) time and exponential space, for a constant ε d ′ depending only on d . The algorithm for minimum weight Hamiltonian cycle generalizes the recent results of Björklund et al. [TALG 2012] on graphs of bounded degree. [ABSTRACT FROM AUTHOR]

The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z, Z, asks whether it is possible to find disjoint sets A, A, such that Z⊆ A, Z⊆ A and A, A induce connected subgraphs. While the naive algorithm runs in O(2 n) time, solutions with complexity of form O((2− ε)) have been found only for special graph classes (van 't Hof et al. in Theor. Comput. Sci. 410(47-49):4834-4843, ; Paulusma and van Rooij in Theor. Comput. Sci. 412(48):6761-6769, ). In this paper we present an O(1.933) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2 barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel. [ABSTRACT FROM AUTHOR]

Let η≥0 be an integer and G be a graph. A set X⊆ V( G) is called a η- treewidth modulator in G if G∖ X has treewidth at most η. Note that a 0-treewidth modulator is a vertex cover, while a 1-treewidth modulator is a feedback vertex set of G. In the η/ ρ- Treewidth Modulator problem we are given an undirected graph G, a ρ-treewidth modulator X⊆ V( G) in G, and an integer ℓ and the objective is to determine whether there exists an η-treewidth modulator Z⊆ V( G) in G of size at most ℓ. In this paper we study the kernelization complexity of η/ ρ- Treewidth Modulator parameterized by the size of X. We show that for every fixed η and ρ that either satisfy 1≤ η< ρ, or η=0 and 2≤ ρ, the η/ ρ- Treewidth Modulator problem does not admit a polynomial kernel unless NP⊆coNP/poly. This resolves an open problem raised by Bodlaender and Jansen (STACS, pp. 177-188, ). Finally, we complement our kernelization lower bounds by showing that ρ/0- Treewidth Modulator admits a polynomial kernel for any fixed ρ. [ABSTRACT FROM AUTHOR]

The famous conjecture of Lovász and Plummer, very recently proven by Esperet et al. (2011), asserts that every cubic bridgeless graph has exponentially many perfect matchings. In this paper we improve the bound of Esperet et al. for a specific subclass of cubic bridgeless graphs called the Klee-graphs. We show that every Klee-graph with n ≥ 8 vertices has at least 3 ⋅ 2 (n+12)/60 perfect matchings. [ABSTRACT FROM AUTHOR]

The classical Feedback Vertex Set problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G. Feedback Vertex SET has attracted a large amount of research in the parameterized setting, and subsequent fixed-parameter and kernelization algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex SET (Subset-FVS), where an instance comes additionally with a set S ⊆ V of vertices, and we ask for a set of at most k vertices that hits all simple cycles passing through S. Because of its applications in circuit testing and genetic linkage analysis, Subset-FVS was studied from the approximation algorithm perspective by Even et al. [SIAM J. Discrete Math., 13 (2000), pp. 225-267; SIAM J. Comput., 30 (2000), pp. 1231-1252]. The question of whether the Subset-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parameterized by |S|. Next we present an algorithm which reduces the given instance to 2knO(1) instances with the size of S bounded by O(k³), using kernelization techniques such as the 2-expansion lemma, Menger's theorem, and Gallai's theorem. These two facts allow us to give a 2O(k log k)nO(1) time algorithm solving the Subset-FVS problem, proving that it is indeed fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

Abstract: The well-known conjecture of Vizing on the domination number of Cartesian product graphs claims that for any two graphs and , . We disprove its variations on independent domination number and Barcalkin–German number, i.e. Conjectures 9.6 and 9.2 from the recent survey Brešar et al. (2012) . We also give some extensions of the double-projection argument of Clark and Suen (2000) , showing that their result can be improved in the case of bounded-degree graphs. Similarly, for rainbow domination number we show for every that , which is closely related to Question 9.9 from the same survey. We also prove that the minimum possible counterexample to Vizing’s conjecture cannot have two neighboring vertices of degree two. [Copyright &y& Elsevier]

Abstract: In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the Bandwidth problem) and for finding an embedding of a given graph into a line that minimizes distortion (the Distortion problem). For both problems we develop algorithms that work in time and polynomial space. For Bandwidth, this improves algorithm by Feige and Kilian from 2000, for Distortion this is the first polynomial space exact algorithm that works in time we are aware of. As a byproduct, we enhance the —time and —space algorithm for Distortion by Fomin et al. to an algorithm working in —time and space. [Copyright &y& Elsevier]

Abstract: The lower and the upper irredundance numbers of a graph G, denoted and , respectively, are conceptually linked to the domination and independence numbers and have numerous relations to other graph parameters. It has been an open question whether determining these numbers for a graph G on n vertices admits exact algorithms running in time faster than the trivial enumeration, also called the -barrier. The main contributions of this article are exact exponential-time algorithms breaking the -barrier for irredundance. We establish algorithms with running times of for computing and for computing . Both algorithms use polynomial space. The first algorithm uses a parameterized approach to obtain (faster) exact algorithms. The second one is based, in addition, on a reduction to the Maximum Induced Matching problem providing a branch-and-reduce algorithm to solve it. [Copyright &y& Elsevier]

Abstract: We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses time and polynomial space to decide whether a claw-free graph on vertices has a dominating set of size at most . Note that this parameterization of Dominating Set is -hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general. The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of -free graphs, which exclude, for some fixed , the complete bipartite graph as a subgraph. For , the class of claw-free graphs and any class of -free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable. We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any , the Dominating Set problem parameterized by the solution size is -hard in graphs that exclude the -claw as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are -hard in these graph classes. Finally, we show that for any , the Clique problem parameterized by solution size, which is -hard on general graphs, is FPT in -claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors. [Copyright &y& Elsevier]

Abstract: For a simple graph with vertices and edges, the inequality , where and are the first and the second Zagreb indices of , is known as the Zagreb indices inequality. A set is good if for every graph whose degrees of vertices are in , the inequality holds. We characterize that an interval is good if and only if or . We also present an algorithm that decides if an arbitrary set of cardinality is good, which requires time and space. [Copyright &y& Elsevier]