Search

Global solar irradiance (GSI) is a fundamental source of energy on Earth. Despite its importance, sunshine or solar irradiance data are rarely available from weather stations. In the absence of available data, there are empirical methods that can be used to estimate solar irradiance. The objective of this study is to calibrate the parameters and to evaluate the performance of four empirical models of solar irradiance estimation (those of Chen, Hargreaves, Hunt, and Richardson) from air temperature data for eight localities in the state of Paraná, Brazil. Data were obtained from the Meteorological Database for Teaching and Research (BDMEP). For the comparison of means among the models, the Kruskal-Wallis non-parametric test was used. Dunn’s multiple comparison tests were used to analyze which models presented different means from the others. The performance of each model was assessed using the indices Pearson correlation coefficient (r), mean bias error (MBE), root mean square error (RMSE), Wilmott concordance index (d), performance index (c) and the Nash-Sutcliffe efficiency (NSE) coefficient. It was observed that the models proposed by Chen and Hunt presented the best performances in the estimation of GSI for the studied Paraná state localities, given that they yielded results which are closer to the observed historical data.

On the occasion of Hans Bodlaender’s 60th birthday, I give a personal account of our history and work together on the technique of cross-composition for kernelization lower bounds. I present several simple new proofs for polynomial kernelization lower bounds using cross-composition, interlaced with personal anecdotes about my time as Hans’ PhD student at Utrecht University. Concretely, I will prove that Vertex Cover, Feedback Vertex Set, and the H-Factor problem for every graph H that has a connected component of at least three vertices, do not admit kernels of $$\mathcal {O}(n^{2-\varepsilon })$$ O ( n 2 - ε ) bits when parameterized by the number of vertices n for any $$\varepsilon > 0$$ ε > 0 , unless $$\mathsf {NP \subseteq coNP/poly}$$ NP ⊆ coNP / poly . These lower bounds are obtained by elementary gadget constructions, in particular avoiding the use of the Packing Lemma by Dell and van Melkebeek.

We study the NP-complete Minimum Shared Edges (MSE) problem. Given an undirected graph, a source and a sink vertex, and two integers p and k, the question is whether there are p paths in the graph connecting the source with the sink and sharing at most k edges. Herein, an edge is shared if it appears in at least two paths. We show that MSE is W[1]-hard when parameterized by the treewidth of the input graph and the number k of shared edges combined. We show that MSE is fixed-parameter tractable with respect to p, but does not admit a polynomial-size kernel (unless NP is contained in coNP/poly). In the proof of the fixed-parameter tractability of MSE parameterized by p, we employ the treewidth reduction technique due to Marx, O'Sullivan, and Razgon [ACM TALG 2013]., 35 pages, 16 figures

In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of a chordal graph is at most \(1.7549^n\), and these can be enumerated in time \(O(1.7549^n)\). For interval graphs, we achieve the better upper bound of \(1.6957^n\) for the number of maximal irredundant sets and we show that they can be enumerated in time \(O(1.6957^n)\). Finally, we show that forests have at most \(1.6181^n\) maximal irredundant sets that can be enumerated in time \(O(1.6181^n)\). We complement the latter result by providing a family of forests having at least \(1.5292^n\) maximal irredundant sets.

International audience; We present a new technique for designing FPT algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s,t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals $s$ and $t$. More precisely, we consider problems where an (unknown) solution is a set $Z \subseteq E(G)$ of size at most $k$ such that (1) in $G-Z$, $s$ and $t$ are in distinct connected components, (2) every edge of $Z$ connects two distinct connected components of $G-Z$, and (3) if we define the set $Z_{s,t} \subseteq Z$ as these edges $e \in Z$ for which there exists an $(s,t)$-path $P_e$ with $E(P_e) \cap Z = \{e\}$, then $Z_{s,t}$ separates $s$ from $t$. We prove that in this scenario one can in randomized time $k^{O(1)} (|V(G)|+|E(G)|)$ add a number of edges to the graph so that with $2^{-O(k \log k)}$ probability no added edge connects two components of $G-Z$ and $Z_{s,t}$ becomes a minimum cut between $s$ and $t$. We apply our method to obtain a randomized FPT algorithm for a notorious "hard nut" graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems, and was unamenable to other techniques for parameterized algorithms in graph cut problems, such as Randomized Contractions, Treewidth Reduction or Shadow Removal. To demonstrate the power of the approach, we consider more generally Min SAT($\Gamma$), parameterized by the solution cost. We show that every problem Min SAT($\Gamma$) is either (1) FPT, (2) W[1]-hard, or (3) able to express the soft constraint $(u \to v)$, and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut.

An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions., LIPIcs, Vol. 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), pages 37:1-37:18

Mathematical programming (2020). doi:10.1007/s10107-020-01495-0, Published by Springer, Berlin ; Heidelberg

Enumerating objects of specified type is one of the principal tasks in algorithms. In graph algorithms an often studied task is the enumeration of vertex subsets of the input graph satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input chordal graph. We establish an enumeration algorithm running in time O ( 1 . 473 6 n ) improving upon a previous O ( 1 . 715 9 n ) algorithm (Golovach et al., 2016) . This is used to show that every n -vertex chordal graph has at most 1 . 473 6 n minimal connected dominating sets.

Domination is one of the classical subjects in structural graph theory and in graph algorithms. The Minimum Dominating Set problem and many of its variants are NP-complete and have been studied from various algorithmic perspectives. One of those variants called irredundance is highly related to domination. For example, every minimal dominating set of a graph G is also a maximal irredundant set of G. In this paper we study the enumeration of the maximal irredundant sets of a claw-free graph. We show that an n-vertex claw-free graph has O ( 1.9341 n ) maximal irredundant sets and these sets can be enumerated in the same time. We complement the aforementioned upper bound with a lower bound by providing a family of graphs having 1.5848 n maximal irredundant sets.

We consider the Weak Roman Domination problem. Given an undirected graph G = ( V , E ) , the aim is to find a weak Roman domination function (wrd-function for short) of minimum cost, i.e. a function f : V → { 0 , 1 , 2 } such that every vertex v ∈ V is defended (i.e. there exists a neighbor u of v , possibly u = v , such that f ( u ) ⩾ 1 ) and for every vertex v ∈ V with f ( v ) = 0 there exists a neighbor u of v such that f ( u ) ⩾ 1 and the function f u → v defined by f u → v ( v ) = 1 , f u → v ( u ) = f ( u ) − 1 and f u → v ( x ) = f ( x ) otherwise does not contain any undefended vertex. The cost of a wrd-function f is defined by c o s t ( f ) = ∑ v ∈ V f ( v ) . The trivial enumeration algorithm runs in time O ∗ ( 3 n ) and polynomial space and is the best one known for the problem so far. We are breaking the trivial enumeration barrier by providing two faster algorithms: we first prove that the problem can be solved in O ∗ ( 2 n ) time needing exponential space, and then describe an O ∗ ( 2 . 227 9 n ) algorithm using polynomial space. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the Red-Blue Dominating Set problem. Moreover we show that the problem can be solved in linear-time on interval graphs.

A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. We prove that Square Root is O(n)-time solvable for graphs of maximum degree 5 and O(n4)-time solvable for graphs of maximum degree at most 6.

We introduce and study the Minimum Feasible Tileset problem: given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario can be formed by selecting at most one symbol from each tile. We show that this problem is $$\mathsf {APX}$$ -hard and that it is $$\mathsf {NP}$$ -hard even if each scenario contains at most three symbols. Our main result is a 4/3-approximation algorithm for the general case. In addition, we show that the Minimum Feasible Tileset problem is fixed-parameter tractable both when parameterized with the number of scenarios and with the number of symbols.

Given a task that requires some skills and a social network of individuals with different skills, the Team Formation problem asks to find a team of individuals that together can perform the task, while minimizing communication costs. Since the problem is NP-hard, we identify the source of intractability by analyzing its parameterized complexity with respect to parameters such as the total number of skills k, the team size l, the communication cost budget b, and the maximum vertex degree \(\varDelta \). We show that the computational complexity strongly depends on the communication cost measure: when using the weight of a minimum spanning tree of the subgraph formed by the selected team, we obtain fixed-parameter tractability for example with respect to the parameter k. In contrast, when using the diameter as measure, the problem is intractable with respect to any single parameter; however, combining \(\varDelta \) with either b or l yields fixed-parameter tractability.

In the Vertex Cover problem we are given a graph $G=(V,E)$ and an integer $k$ and have to determine whether there is a set $X\subseteq V$ of size at most $k$ such that each edge in $E$ has at least one endpoint in $X$. The problem can be easily solved in time $O^*(2^k)$, making it fixed-parameter tractable (FPT) with respect to $k$. While the fastest known algorithm takes only time $O^*(1.2738^k)$, much stronger improvements have been obtained by studying parameters that are smaller than $k$. Apart from treewidth-related results, the arguably best algorithm for Vertex Cover runs in time $O^*(2.3146^p)$, where $p=k-LP(G)$ is only the excess of the solution size $k$ over the best fractional vertex cover (Lokshtanov et al.\ TALG 2014). Since $p\leq k$ but $k$ cannot be bounded in terms of $p$ alone, this strictly increases the range of tractable instances. Recently, Garg and Philip (SODA 2016) greatly contributed to understanding the parameterized complexity of the Vertex Cover problem. They prove that $2LP(G)-MM(G)$ is a lower bound for the vertex cover size of $G$, where $MM(G)$ is the size of a largest matching of $G$, and proceed to study parameter $\ell=k-(2LP(G)-MM(G))$. They give an algorithm of running time $O^*(3^\ell)$, proving that Vertex Cover is FPT in $\ell$. It can be easily observed that $\ell\leq p$ whereas $p$ cannot be bounded in terms of $\ell$ alone. We complement the work of Garg and Philip by proving that Vertex Cover admits a randomized polynomial kernelization in terms of $\ell$, i.e., an efficient preprocessing to size polynomial in $\ell$. This improves over parameter $p=k-LP(G)$ for which this was previously known (Kratsch and Wahlstr\"om FOCS 2012)., Comment: Full version of ESA 2016 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,...,\ell$ to some edges and give separate budgets $k_{1},k_{2},...,k_{\ell}$. 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, but also needs to satisfy that $|C\cap E_{i}|\leq k_{i}$ for every $i\in \{1,...,\ell\}$. Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for $\ell = 2$. We propose FPT algorithms parameterized by $k=k_{1}+...+k_{\ell}$ 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 $\ell$-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., Full version of the paper presented at IPEC 2018

We study the enumeration of the minimal dominating sets and upper bounds for the number of such sets in chordal graphs. We show that the maximum number of minimal dominating sets of an n-vertex chordal graph is at most 1.5048 n and prove that these sets can be enumerated in time O ( 1.5048 n ) . In this way we improve the previous upper bound of 1.5214 n , recently established by Abu-Khzam and Heggernes, and narrow the gap between the upper bound and the known lower bound of 1.4422 n .

Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class $${{\mathcal {H}}}$$ . There are both polynomial-time solvable and NP-complete results in this direction, depending on $${{\mathcal {H}}}$$ . We present a general framework for the problem if $$\mathcal{H}$$ is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where $${{\mathcal {H}}}$$ is the class of outerplanar graphs and $${{\mathcal {H}}}$$ is the class of graphs of pathwidth at most 2.

A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. The problem of testing whether a graph admits a square root which belongs to some specified graph class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}$\end{document}ℋ is called the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}$\end{document}ℋ-Square Root problem. By showing boundedness of treewidth we prove that Square Root is polynomial-time solvable on some classes of graphs with small clique number and that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}$\end{document}ℋ-Square Root is polynomial-time solvable when \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}$\end{document}ℋ is the class of cactuses.

We study the complexity of the Graph Isomorphism problem on graph classes that are characterized by a finite number of forbidden induced subgraphs, focusing mostly on the case of two forbidden subgraphs. We show hardness results and develop techniques for the structural analysis of such graph classes, which applied to the case of two forbidden subgraphs give the following results: A dichotomy into isomorphism complete and polynomial-time solvable graph classes for all but finitely many cases, whenever neither of the forbidden graphs is a clique, a pan, or a complement of these graphs. Further reducing the remaining open cases we show that (with respect to graph isomorphism) forbidding a pan is equivalent to forbidding a clique of size three., 22 pages, 4 figures. To appear in the proceedings of WG 2012

In a graph, a matching cut is an edge cut that is a matching. Matching Cut , which is known to be NP-complete, is the problem of deciding whether or not a given graph G has a matching cut. In this paper we show that Matching Cut admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an O ∗ ( 2 dc ( G ) ) -time and an O ∗ ( 2 d c ¯ ( G ) ) -time FPT algorithm for Matching Cut , where dc ( G ) and d c ¯ ( G ) are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve Matching Cut from O ∗ ( 1 . 414 3 n ) to O ∗ ( 1 . 307 1 n ) where n is the number of vertices in G . Moreover, we point out that, unless NP ⊆ coNP ∕ poly , Matching Cut does not admit a polynomial kernel when parameterized simultaneously by treewidth, the number of edges crossing the cut, and the maximum degree of G .

We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics, 2016) and motivated by applications of overlap graphs in bioinformatics. The behavior of the parameter is poorly understood. The complexity of computing it is open and it is not known whether the decision version of the problem is in NP. The only known upper bound on the readability of a bipartite graph (following from a work of Braga and Meidanis, LATIN 2002) is exponential in the maximum degree of the graph. Graphs that arise in bioinformatic applications have low readability. In this paper, we focus on graph families with readability $o(n)$, where $n$ is the number of vertices. We show that the readability of $n$-vertex bipartite chain graphs is between $\Omega(\log n)$ and $O(\sqrt{n})$. We give an efficiently testable characterization of bipartite graphs of readability at most $2$ and completely determine the readability of grids, showing in particular that their readability never exceeds $3$. As a consequence, we obtain a polynomial time algorithm to determine the readability of induced subgraphs of grids. One of the highlights of our techniques is the appearance of Euler's totient function in the analysis of the readability of bipartite chain graphs. We also develop a new technique for proving lower bounds on readability, which is applicable to dense graphs with a large number of distinct degrees., Comment: 16 pages (including references) and 5 figures

Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 n )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) k n O(logk))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to $O(4^{k}n^{O(\log^{2} k)})$ . This improves on trivial enumeration for roughly k

For a finite set Γ of Boolean relations, M ax O nes SAT(Γ) and E xact O nes SAT(Γ) are generalized satisfiability problems where every constraint relation is from Γ, and the task is to find a satisfying assignment with at least/exactly k variables set to 1, respectively. We study the parameterized complexity of these problems, including the question whether they admit polynomial kernels. For M ax O nes SAT(Γ), we give a classification into five different complexity levels: polynomial-time solvable, admits a polynomial kernel, fixed-parameter tractable, solvable in polynomial time for fixed k , and NP-hard already for k = 1. For E xact O nes SAT(Γ), we refine the classification obtained earlier by taking a closer look at the fixed-parameter tractable cases and classifying the sets Γ for which E xact O nes SAT(Γ) admits a polynomial kernel.

We show that all minimal dominating sets of a chordal bipartite graph can be generated in incremental polynomial, hence output polynomial, time. Enumeration of minimal dominating sets in graphs is equivalent to enumeration of minimal transversals in hypergraphs. Whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a well-studied and challenging question that has been open for several decades. With this result we contribute to the known cases having an affirmative reply to this important question.

The $$k$$k-colouring reconfiguration problem asks whether, for a given graph $$G$$G, two proper $$k$$k-colourings $$\alpha $$ź and $$\beta $$β of $$G$$G, and a positive integer $$\ell $$l, there exists a sequence of at most $$\ell +1$$l+1 proper $$k$$k-colourings of $$G$$G which starts with $$\alpha $$ź and ends with $$\beta $$β and where successive colourings in the sequence differ on exactly one vertex of $$G$$G. We give a complete picture of the parameterized complexity of the $$k$$k-colouring reconfiguration problem for each fixed $$k$$k when parameterized by $$\ell $$l. First we show that the $$k$$k-colouring reconfiguration problem is polynomial-time solvable for $$k=3$$k=3, settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all $$k \ge 4$$kź4, we show that the $$k$$k-colouring reconfiguration problem, when parameterized by $$\ell $$l, is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.

The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this paper we study output-polynomial enumeration algorithms on graphs of bounded LMIM-width and graphs of bounded local LMIM-width. In particular, we show that all 1-minimal and all 1-maximal $$(\sigma ,\rho )$$ -dominating sets, and hence all minimal dominating sets, of graphs of bounded LMIM-width can be enumerated with polynomial (linear) delay using polynomial space. Furthermore, we show that all minimal dominating sets of a unit square graph can be enumerated in incremental polynomial time.

The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan -- an assignment of tasks to authorized users -- such that all constraints are satisfied. The WSP is, in fact, the conservative Constraint Satisfaction Problem (i.e., for each variable, here called task, we have a unary authorization constraint) and is, thus, NP-complete. It was observed by Wang and Li (2010) that the number k of tasks is often quite small and so can be used as a parameter, and several subsequent works have studied the parameterized complexity of WSP regarding parameter k. We take a more detailed look at the kernelization complexity of WSP(\Gamma) when \Gamma\ denotes a finite or infinite set of allowed constraints. Our main result is a dichotomy for the case that all constraints in \Gamma\ are regular: (1) We are able to reduce the number n of users to n', Comment: An extended abstract appears in the proceedings of IPEC 2014

This work further explores the applications of co-nondeterminism for showing kernelization lower bounds. The only known example prior to this work excludes polynomial kernelizations for the so-called Ramsey problem of finding an independent set or a clique of at least k vertices in a given graph [Kratsch 2012]. We study the more general problem of finding induced subgraphs on k vertices fulfilling some hereditary property Π, called Π-Induced Subgraph. The problem is NP-hard for all nontrivial choices of Π by a classic result of Lewis and Yannakakis [1980]. The parameterized complexity of this problem was classified by Khot and Raman [2002] depending on the choice of Π. The interesting cases for kernelization are for Π containing all independent sets and all cliques, since the problem is trivially polynomial time solvable or W[1]-hard otherwise. Our results are twofold. Regarding Π-Induced Subgraph, we show that for a large choice of natural graph properties Π, including chordal, perfect, cluster, and cograph, there is no polynomial kernel with respect to k . This is established by two theorems, each one capturing different (but not necessarily exclusive) sets of properties: one using a co-nondeterministic variant of OR-cross-composition and one by a polynomial parameter transformation from Ramsey. Additionally, we show how to use improvement versions of NP-hard problems as source problems for lower bounds, without requiring their NP-hardness. For example, for Π-Induced Subgraph our compositions may assume existing solutions of size k--1. This follows from the more general fact that source problems for OR-(cross-)compositions need only be NP-hard under co-nondeterministic reductions. We believe this to be useful for further lower-bound proofs, for example, since improvement versions simplify the construction of a disjunction (OR) of instances required in compositions. This adds a second way of using co-nondeterminism for lower bounds.

Kernelization is a theoretical formalization of efficient preprocessing for NP-hard problems. Empirically, preprocessing is highly successful in practice, for example in state-of-the-art ILP-solvers like CPLEX. Motivated by this, previous work studied the existence of kernelizations for ILP related problems, e.g., for testing feasibility of Ax¿=¿b. In contrast to the observed success of CPLEX, however, the results were largely negative. Intuitively, practical instances have far more useful structure than the worst-case instances used to prove these lower bounds. In the present paper, we study the effect that subsystems that have (a Gaifman graph of) bounded treewidth or that are totally unimodular have on the kernelizability of the ILP feasibility problem. We show that, on the positive side, if these subsystems have a small number of variables on which they interact with the remaining instance, then we can efficiently replace them by smaller subsystems of size polynomial in the domain without changing feasibility. Thus, if large parts of an instance consist of such subsystems, then this yields a substantial size reduction. Complementing this we prove that relaxations to the considered structures, e.g., larger boundaries of the subsystems, allow worst-case lower bounds against kernelization. Thus, these relaxed structures give rise to instance families that cannot be efficiently reduced, by any approach.

In the game of Kayles, two players select alternatingly a vertex from a given graph G, but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyze the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W ? V is a K-set in a graph G = ( V , E ) , if G W is connected and there exists an independent set X such that W = V - N X . The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G. We prove that the number of K-sets in a graph with n vertices is bounded by O ( 1.6052 n ) . A computer-generated case analysis improves this bound to O ( 1.6031 n ) K-sets, and thus we have an upper bound of O ( 1.6031 n ) on the running time of the algorithm for Kayles. We also show that the number of K-sets in a tree is bounded by n ? 3 n / 3 and thus Kayles can be solved on trees in O ( 1.4423 n ) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp.As corollaries, we obtain that determining which player has a winning strategy in the games G avoid ( POS DNF 2 ) and G seek ( POSDNF 3 ) can also be determined in O ( 1.6031 n ) time. In G avoid ( POSDNF 2 ) , we have a positive formula F on n Boolean variables in Disjunctive Normal Form with two variables per clause. Initially, all variables are false, and players alternately set a variable from false to true; the first player that makes F true loses the game. The game G seek ( POSDNF 3 ) is similar, but now there are three variables per clause, and the first player that makes F true wins the game.

Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem is NP-complete in general, and consequently substantial effort has been dedicated to deciding whether a given graph has a square root that belongs to a particular graph class. There are both polynomial-time solvable and NP-complete cases, depending on the graph class. We contribute with new results in this direction. Given an arbitrary input graph G, we give polynomial-time algorithms to decide whether G has an outerplanar square root, and whether G has a square root that is of pathwidth at most 2.

In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of a chordal graph is at most \(1.7549^n\), and these can be enumerated in time \(O(1.7549^n)\). For interval graphs, we achieve the better upper bound of \(1.6957^n\) for the number of maximal irredundant sets and we show that they can be enumerated in time \(O(1.6957^n)\). Finally, we show that forests have at most \(1.6181^n\) maximal irredundant sets that can be enumerated in time \(O(1.6181^n)\). We complement the latter result by providing a family of forests having at least \(1.5292^n\) maximal irredundant sets.

Tropical Connected Set is strongly related to the Graph Motif problem which deals with vertex-colored graphs. Graph Motif has various applications in biology and metabolic networks, and has widely been studied in the last twenty years.The input of the Tropical Connected Set problem is a vertex-colored graph (G,c), where G=(V,E) is a graph and c is a vertex coloring assigning to each vertex of G a color. The task is to find a connected subset SV of minimum size such that each color of G appears in S. This problem is known to be NP-complete, even when restricted to trees of height at most three. We study exact exponential algorithms to solve Tropical Connected Set. We present an O(1.5359n) time algorithm for general graphs and an O(1.2721n) time algorithm for trees. We also show that Tropical Connected Set on trees has no sub-exponential algorithm unless the Exponential Time Hypothesis fails.

Domination is one of the classical subjects in structural graph theory and in graph algorithms. The Minimum Dominating Set problem and many of its variants are NP-complete and have been studied from various algorithmic perspectives. One of those variants called irredundance is highly related to domination. For example, every minimal dominating set of a graph G is also a maximal irredundant set of G. In this paper we study the enumeration of the maximal irredundant sets of a claw-free graph. We show that an n-vertex claw-free graph has \(O(1.9341^n)\) maximal irredundant sets and these sets can be enumerated in the same time. We complement the aforementioned upper bound with a lower bound by providing a family of graphs having \(1.5848^n\) maximal irredundant sets.

For a positive integer s , an s -club in a graph G is a set of vertices that induces a subgraph of G of diameter at most s . We study a relation of clubs and cliques. For a positive integer s , we say that a graph class G has the s -clique-power property if for every graph G ∈ G , every maximal clique in G s is an s -club in G . Our main combinatorial results show that both 4-chordal graphs and AT-free graphs have the s -clique-power property for all s ≥ 2 . This has various algorithmic consequences. In particular we show that a maximum s -club in G can be computed in polynomial time when G is a chordal bipartite or a strongly chordal or a distance hereditary graph. On weakly chordal graphs, we obtain a polynomial-time algorithm when s is an odd integer, which is best possible as the problem is NP-hard for even values of s . We complement these results by proving the NP-hardness of the problem for every fixed s on 4-chordal graphs. Finally, if G is an AT-free graph, we prove that the problem can be solved in polynomial time when s ≥ 2 , which gives an interesting contrast to the fact that the problem is NP-hard for s = 1 on this graph class.

The framework of Bodlaender et al. (J Comput Sys Sci 75(8):423---434, 2009) and Fortnow and Santhanam (J Comput Sys Sci 77(1):91---106, 2011) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, some issues are not addressed by this framework, including the existence of Turing kernels such as the "kernelization" of leaf out-branching $$(k)$$ ( k ) that outputs $$n$$ n instances each of size poly $$(k)$$ ( k ) . Observing that Turing kernels are preserved by polynomial parametric transformations (PPTs), we define two kernelization hardness hierarchies by the PPT-closure of problems that seem fundamentally unlikely to admit efficient Turing kernelizations. This gives rise to the MK- and WK-hierarchies which are akin to the M- and W-hierarchies of parameterized complexity. We find that several previously considered problems are complete for the fundamental hardness class WK[1], including Min Ones $$d$$ d -SAT $$(k)$$ ( k ) , Binary NDTM Halting $$(k)$$ ( k ) , Connected Vertex Cover $$(k)$$ ( k ) , and Clique parameterized by $$k \log n$$ k log n . We conjecture that no WK[1]-hard problem admits a polynomial Turing kernel. Our hierarchy subsumes an earlier hierarchy of Harnik and Naor that, from a parameterized perspective, is restricted to classical problems parameterized by witness size. Our results provide the first natural complete problems for, e.g., their class $$VC_1$$ V C 1 ; this had been left open.

Given a graph G = ( V , E ) and a set S ⊆ V , a set U ⊆ V is a subset feedback vertex set of ( G , S ) if no cycle in G [ V ∖ U ] contains a vertex of S . The Subset Feedback Vertex Set problem takes as input G , S , and an integer k , and the question is whether ( G , S ) has a subset feedback vertex set of cardinality or weight at most k . Both the weighted and the unweighted versions of this problem are NP-complete on chordal graphs, even on their subclass split graphs. We give an algorithm with running time O ( 1.6708 n ) that enumerates all minimal subset feedback vertex sets on chordal graphs on n vertices. As a consequence, Subset Feedback Vertex Set can be solved in time O ( 1.6708 n ) on chordal graphs, both in the weighted and in the unweighted case. As a comparison, on arbitrary graphs the fastest known algorithm for these problems has O ( 1.8638 n ) running time. We also obtain that a chordal graph G has at most 1.6708 n minimal subset feedback vertex sets, regardless of S . This narrows the gap with respect to the best known lower bound of 1.5848 n on this graph class. For arbitrary graphs, the gap is substantially wider, as the best known upper and lower bounds are 1.8638 n and 1.5927 n , respectively.

We show that all minimal edge dominating sets of a graph can be generated in incremental polynomial time. We present an algorithm that solves the equivalent problem of enumerating minimal (vertex) dominating sets of line graphs in incremental polynomial, and consequently output polynomial, time. Enumeration of minimal dominating sets in graphs has recently been shown to be equivalent to enumeration of minimal transversals in hypergraphs. The question whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a fundamental and challenging question; it has been open for several decades and has triggered extensive research. To obtain our result, we present a flipping method to generate all minimal dominating sets of a graph. Its basic idea is to apply a flipping operation to a minimal dominating set $$D^*$$D? to generate minimal dominating sets $$D$$D such that $$G[D]$$G[D] contains more edges than $$G[D^*]$$G[D?]. We show that the flipping method works efficiently on line graphs, resulting in an algorithm with delay $$O(n^2m^2|\mathcal {L}|)$$O(n2m2|L|) between each pair of consecutively output minimal dominating sets, where $$n$$n and $$m$$m are the numbers of vertices and edges of the input graph, respectively, and $$\mathcal {L}$$L is the set of already generated minimal dominating sets. Furthermore, we are able to improve the delay to $$O(n^2m|\mathcal {L}|)$$O(n2m|L|) on line graphs of bipartite graphs. Finally we show that the flipping method is also efficient on graphs of large girth, resulting in an incremental polynomial time algorithm to enumerate the minimal dominating sets of graphs of girth at least 7.

We introduce the cross-composition framework for proving kernelization lower bounds. A classical problem L AND/OR-cross-composes into a parameterized problem Q if it is possible to efficiently construct an instance of Q with polynomially bounded parameter value that expresses the logical AND or OR of a sequence of instances of L. Building on work by Bodlaender et al. (ICALP 2008) and using a result by Fortnow and Santhanam (STOC 2008) with a refinement by Dell and van Melkebeek (STOC 2010), we show that if an NP-hard problem OR-cross-composes into a parameterized problem Q then Q does not admit a polynomial kernel unless NP \subseteq coNP/poly and the polynomial hierarchy collapses. Similarly, an AND-cross-composition for Q rules out polynomial kernels for Q under Bodlaender et al.'s AND-distillation conjecture. Our technique generalizes and strengthens the recent techniques of using composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (non-standard) parameterizations, e.g., Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. After learning of our results, several teams of authors have successfully applied the cross-composition framework to different parameterized problems. For completeness, our presentation of the framework includes several extensions based on this follow-up work. For example, we show how a relaxed version of OR-cross-compositions may be used to give lower bounds on the degree of the polynomial in the kernel size., Comment: A preliminary version appeared in the proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) under the title "Cross-Composition: A New Technique for Kernelization Lower Bounds". Several results have been strengthened compared to the preliminary version (http://arxiv.org/abs/1011.4224). 29 pages, 2 figures

Planar graphs are known to have geometric representations of various types, e.g. as contacts of disks, triangles or - in the bipartite case - vertical and horizontal segments. It is known that such representations can be drawn in linear time, we here wonder whether it is as easy to decide whether a partial representation can be completed to a representation of the whole graph. We show that in each of the cases above, this problem becomes NP-hard. These are the first classes of geometric graphs where extending partial representations is provably harder than recognition, as opposed to e.g. interval graphs, circle graphs, permutation graphs or even standard representations of plane graphs.On the positive side we give two polynomial time algorithms for the grid contact case. The first one is for the case when all vertical segments are pre-represented (note: the problem remains NP-complete when a subset of the vertical segments is specified, even if none of the horizontals are). Secondly, we show that the case when the vertical segments have only their x-coordinates specified (i.e., they are ordered horizontally) is polynomially equivalent to level planarity, which is known to be solvable in polynomial time.

Vertex deletion problems are at the heart of parameterized complexity. For a graph class F, the F-Deletion problem takes as input a graph G and an integer k. The question is whether it is possible to delete at most k vertices from G such that the resulting graph belongs to F. Whether Perfect Deletion is fixed-parameter tractable, and whether Chordal Deletion admits a polynomial kernel, when parameterized by k, have been stated as open questions in previous work. We show that Perfect Deletion and Weakly Chordal Deletion are W[2]-hard when parameterized by k. In search of positive results, we study a restricted variant of the F-Deletion problem. In this restricted variant, the deleted vertices must be taken from a specified set X, and we parameterize by |X|. We show that for Perfect Deletion and Weakly Chordal Deletion, although this restriction immediately ensures fixed-parameter tractability, it is not enough to yield polynomial kernels, unless NP @? coNP/poly. On the positive side, for Chordal Deletion, the restriction enables us to obtain a kernel with O(|X|^4) vertices.

Given a permutation @p of {1,...,n} and a positive integer k, can @p be partitioned into at most k subsequences, each of which is either increasing or decreasing? We give an algorithm with running time 2^O^(^k^^^2^l^o^g^k^)n^O^(^1^) that solves this problem, thereby showing that it is fixed parameter tractable. This NP-complete problem is equivalent to deciding whether the cochromatic number of a given permutation graph on n vertices is at most k. Our algorithm solves in fact a more general problem: within the mentioned running time, it decides whether the cochromatic number of a given perfect graph on n vertices is at most k. To obtain our result we use a combination of two well-known techniques within parameterized algorithms: iterative compression and greedy localization. Consequently we name this combination ''iterative localization''. We further demonstrate the power of this combination by giving an algorithm with running time 2^O^(^k^^^2^l^o^g^k^)nlogn that decides whether a given set of n non-overlapping axis-parallel rectangles can be stabbed by at most k of a given set of horizontal and vertical lines.

Given a graph G and an integer k , the Π Edge Completion/Editing/Deletion problem asks whether it is possible to add, edit, or delete at most k edges in G such that one obtains a graph that fulfills the property Π . Edge modification problems have received considerable interest from a parameterized point of view. When parameterized by k , many of these problems turned out to be fixed-parameter tractable and some are known to admit polynomial kernelizations, i.e., efficient preprocessing with a size guarantee that is polynomial in k . This paper answers an open problem posed by Cai (IWPEC 2006) [11] , namely, whether the Π Edge Deletion problem, parameterized by the number of deletions, admits a polynomial kernelization when Π can be characterized by a finite set of forbidden induced subgraphs. We answer this question negatively based on the framework for kernelization lower bounds of Bodlaender et al. (ICALP 2008, JCSS 2009) [15] and Fortnow and Santhanam (STOC 2008, JCSS 2011) [16] . We present a graph H on seven vertices such that H -free Edge Deletion and H -free Edge Editing do not admit polynomial kernelizations, unless NP ⊆ coNP / poly . The application of the framework is not immediate and requires a lower bound for a Not-1-in-3 SAT problem that may be of independent interest.

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k-Coloring problem requires in addition that every vertex u must receive a color from some given set L(u)⊆{1,?,k}. Let P n denote the path on n vertices, and G+H and rH the disjoint union of two graphs G and H and r copies of H, respectively. For any two fixed integers k and r, we show that List k-Coloring can be solved in polynomial time for graphs with no induced rP 1+P 5, hereby extending the result of Hoang, Kaminski, Lozin, Sawada and Shu for graphs with no induced P 5. Our result is tight; we prove that for any graph H that is a supergraph of P 1+P 5 with at least 5 edges, already List 5-Coloring is NP-complete for graphs with no induced H.

We consider the problem of finding a subcomplex K' of a simplicial complex K such that K' is homeomorphic to the 2-dimensional sphere, S^2. We study two variants of this problem. The first asks if there exists such a K' with at most k triangles, and we show that this variant is W[1]-hard and, assuming ETH, admits no O(n^{o(sqrt(k))}) time algorithm. We also give an algorithm that is tight with regards to this lower bound. The second problem is the dual of the first, and asks if K' can be found by removing at most k triangles from K. This variant has an immediate O(3^k poly(|K|)) time algorithm, and we show that it admits a polynomial kernelization to O(k^2) triangles, as well as a polynomial compression to a weighted version with bit-size O(k log k)., A preliminary version of this paper appeared in Proc. of 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

We show that interval graphs on n vertices have at most 3 n / 3 ≈ 1.442 2 n minimal dominating sets, and that these can be enumerated in time O ∗ ( 3 n / 3 ) . As there are examples of interval graphs that actually have 3 n / 3 minimal dominating sets, our bound is tight. We show that the same upper bound holds also for trees, i.e. trees on n vertices have at most 3 n / 3 ≈ 1.442 2 n minimal dominating sets. The previous best upper bound on the number of minimal dominating sets in trees was 1.465 6 n , and there are trees that have 1.416 7 n minimal dominating sets. Hence our result narrows this gap. On general graphs there is a larger gap, with 1.715 9 n being the best known upper bound, whereas no graph with 1.570 5 n or more minimal dominating sets is known.

As Bin Packing is NP-hard already for k=2 bins, it is unlikely to be solvable in polynomial time even if the number of bins is a fixed constant. However, if the sizes of the items are polynomially bounded integers, then the problem can be solved in time n^O^(^k^) for an input of length n by dynamic programming. We show, by proving the W[1]-hardness of Unary Bin Packing (where the sizes are given in unary encoding), that this running time cannot be improved to f(k)@?n^O^(^1^) for any function f(k) (under standard complexity assumptions). On the other hand, we provide an algorithm for Bin Packing that obtains in time 2^O^(^k^l^o^g^^^2^k^)+O(n) a solution with additive error at most 1, i.e., either finds a packing into k+1 bins or decides that k bins do not suffice.

The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. By researching boundedness of the treewidth of a graph, we prove that Square Root is polynomial-time solvable on various graph classes of low clique number that are not minor-closed.

The Subset Feedback Vertex Set problem takes as input a pair (G,S), where G=(V,E) is a graph with weights on its vertices, and S⊆V. The task is to find a set of vertices of total minimum weight to be removed from G, such that in the remaining graph no cycle contains a vertex of S. We show that this problem can be solved in time O(1.8638 n ), where n=|V|. This is a consequence of the main result of this paper, namely that all minimal subset feedback vertex sets of a graph can be enumerated in time O(1.8638 n ).

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The Listk-Coloring problem requires in addition that every vertex u must receive a color from some given set L(u)⊆{1,…,k}L(u)⊆{1,…,k}. Let PnPn denote the path on n vertices, and G+HG+H and rH the disjoint union of two graphs G and H and r copies of H, respectively. We show that Listk-Coloring is fixed-parameter tractable on graphs with no induced rP1+P2rP1+P2 when parameterized by k+rk+r, and that for any fixed integer r, the problem k-Coloring restricted to such graphs allows a polynomial kernel when parameterized by k. Finally, we show that Listk-Coloring is fixed-parameter tractable on graphs with no induced P1+P3P1+P3 when parameterized by k.