Search

We study Steiner Forest on $H$-subgraph-free graphs, that is, graphs that do not contain some fixed graph $H$ as a (not necessarily induced) subgraph. We are motivated by a recent framework that completely characterizes the complexity of many problems on $H$-subgraph-free graphs. However, in contrast to e.g. the related Steiner Tree problem, Steiner Forest falls outside this framework. Hence, the complexity of Steiner Forest on $H$-subgraph-free graphs remained tantalizingly open. In this paper, we make significant progress towards determining the complexity of Steiner Forest on $H$-subgraph-free graphs. Our main results are four novel polynomial-time algorithms for different excluded graphs $H$ that are central to further understand its complexity. Along the way, we study the complexity of Steiner Forest for graphs with a small $c$-deletion set, that is, a small set $S$ of vertices such that each component of $G-S$ has size at most $c$. Using this parameter, we give two noteworthy algorithms that we later employ as subroutines. First, we prove Steiner Forest is FPT parameterized by $|S|$ when $c=1$ (i.e. the vertex cover number). Second, we prove Steiner Forest is polynomial-time solvable for graphs with a 2-deletion set of size at most 2. The latter result is tight, as the problem is NP-complete for graphs with a 3-deletion set of size 2.

We consider a natural generalization of Vertex Cover: the Subset Vertex Cover problem, which is to decide for a graph $G=(V,E)$, a subset $T \subseteq V$ and integer $k$, if $V$ has a subset $S$ of size at most $k$, such that $S$ contains at least one end-vertex of every edge incident to a vertex of $T$. A graph is $H$-free if it does not contain $H$ as an induced subgraph. We solve two open problems from the literature by proving that Subset Vertex Cover is NP-complete on subcubic (claw,diamond)-free planar graphs and on $2$-unipolar graphs, a subclass of $2P_3$-free weakly chordal graphs. Our results show for the first time that Subset Vertex Cover is computationally harder than Vertex Cover (under P $\neq$ NP). We also prove new polynomial time results. We first give a dichotomy on graphs where $G[T]$ is $H$-free. Namely, we show that Subset Vertex Cover is polynomial-time solvable on graphs $G$, for which $G[T]$ is $H$-free, if $H = sP_1 + tP_2$ and NP-complete otherwise. Moreover, we prove that Subset Vertex Cover is polynomial-time solvable for $(sP_1 + P_2 + P_3)$-free graphs and bounded mim-width graphs. By combining our new results with known results we obtain a partial complexity classification for Subset Vertex Cover on $H$-free graphs.

For any particular class of graphs, algorithms for computational problems restricted to the class often rely on structural properties that depend on the specific problem at hand. This begs the question if a large set of such results can be explained by some common problem conditions. We propose such conditions for $HH$-subgraph-free graphs. For a set of graphs $HH$, a graph $G$ is $HH$-subgraph-free if $G$ does not contain any of graph from $H$ as a subgraph. Our conditions are easy to state. A graph problem must be efficiently solvable on graphs of bounded treewidth, computationally hard on subcubic graphs, and computational hardness must be preserved under edge subdivision of subcubic graphs. Our meta-classification says that if a graph problem satisfies all three conditions, then for every finite set $HH$, it is ``efficiently solvable'' on $HH$-subgraph-free graphs if $HH$ contains a disjoint union of one or more paths and subdivided claws, and is ``computationally hard'' otherwise. We illustrate the broad applicability of our meta-classification by obtaining a dichotomy between polynomial-time solvability and NP-completeness for many well-known partitioning, covering and packing problems, network design problems and width parameter problems. For other problems, we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). The proposed framework thus gives a simple pathway to determine the complexity of graph problems on $HH$-subgraph-free graphs. This is confirmed even more by the fact that along the way, we uncover and resolve several open questions from the literature.

We study the maximum geometric independent set and clique problems in the streaming model. Given a collection of geometric objects arriving in an insertion only stream, the aim is to find a subset such that all objects in the subset are pairwise disjoint or intersect respectively. We show that no constant factor approximation algorithm exists to find a maximum set of independent segments or $2$-intervals without using a linear number of bits. Interestingly, our proof only requires a set of segments whose intersection graph is also an interval graph. This reveals an interesting discrepancy between segments and intervals as there does exist a $2$-approximation for finding an independent set of intervals that uses only $O(\alpha(\mathcal{I})\log |\mathcal{I}|)$ bits of memory for a set of intervals $\mathcal{I}$ with $\alpha(\mathcal{I})$ being the size of the largest independent set of $\mathcal{I}$. On the flipside we show that for the geometric clique problem there is no constant-factor approximation algorithm using less than a linear number of bits even for unit intervals. On the positive side we show that the maximum geometric independent set in a set of axis-aligned unit-height rectangles can be $4$-approximated using only $O(\alpha(\mathcal{R})\log |\mathcal{R}|)$ bits., Comment: 11 pages, 3 figures

Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower bounds for the problems of Pi-free Deletion, H-free Deletion, and the more specific forms of Cluster Vertex Deletion and Odd Cycle Transversal. We focus on the complexity in terms of the number of passes over the input stream, and the memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting., Comment: 31 pages, 2 figures, an extended abstract appeared in the proceedings of FCT 2021, see http://doi.org/10.1007/978-3-030-86593-1_29

There are many benefits in providing formal specifications for our software. However, teaching students to do this is not always easy as courses on formal methods are often experienced as dry by students. This paper presents a game called FormalZ that teachers can use to introduce some variation in their class. Students can have some fun in playing the game and, while doing so, also learn the basics of writing formal specifications in the form of pre- and post-conditions. Unlike existing software engineering themed education games such as Pex and Code Defenders, FormalZ takes the deep gamification approach where playing gets a more central role in order to generate more engagement. This short paper presents our work in progress: the first implementation of FormalZ along with the result of a preliminary users' evaluation. This implementation is functionally complete and tested, but the polishing of its user interface is still future work.