Marta Piecyk

Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski

The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, there has been a growing interest in the complexity of such problems in ordered graphs, i.e., graphs with a fixed linear ordering of vertices. Such an approach allows us to investigate the boundary of tractability more closely. However, most results so far concern coloring problems. In this paper, we focus on the complexity of the Maximum Weight Independent Set (MWIS) problem in classes of ordered graphs. For every ordered graph $H$, we classify the complexity of MWIS in ordered graphs that exclude $H$ as an induced subgraph into one of the following cases: (1) solvable in polynomial time, (2) solvable in quasipolynomial time, (3) solvable in subexponential time, (4) NP-hard. Notably, case (3) contains only one well-structured family of $H$ obtained from two nested edges by adding isolated vertices in a specific way. Thus, our results yield an almost complete complexity dichotomy for MWIS in classes of ordered graphs defined by a single forbidden induced subgraph into cases solvable in quasipolynomial time and those that are NP-hard.

Marta Piecyk, R. B. Sandeep

Subdividing an edge $uv$ in a graph replaces it by a path $u w v$ with one new vertex. For a graph $H$, the \textsc{$H$-free Subdivision} problem asks whether, given a graph $G$ and an integer $k$, one can destroy all induced copies of $H$ in $G$ by at most $k$ edge subdivisions. We show that the problem is polynomial-time solvable when every component of $H$ is a subdivided star or a subdivided bistar, and at most one component is a subdivided bistar. On the other hand, we prove that \textsc{$H$-free Subdivision} is NP-complete and, assuming the Exponential Time Hypothesis, admits no $2^{o(k)} n^{O(1)}$-time algorithm whenever $H$ satisfies any of the following conditions: \begin{itemize} \item $H$ has minimum degree at least $2$, and the neighborhood of every degree-$2$ vertex induces a $K_2$; \item the vertices of degree at least $3$ in $H$ induce a graph with at least two edges; \item $H$ has a triangle with two vertices of degree at least $3$; \item $H$ contains, as an induced subgraph, the graph obtained from two vertex-disjoint triangles by adding one edge between them; \item $H$ contains exactly one triangle; \item $H$ has girth at least $4$; \item $H$ is a tree with exactly two vertices of degree at least $3$ at distance $2$ or at least $4$. \end{itemize} A simple bounded search-tree algorithm for the problem runs in $2^{O(k)} n^{O(1)}$ time. Thus, for all hardness cases above, this running time is essentially optimal under ETH.

Václav Blažej, Michał Dębski, Zbigniew Lonc et al.

We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected graph, and sets of goods allocated to the agents are connected subgraphs of this graph. We focus on the widely-studied maximin share criterion of fairness. It has been shown that an allocation satisfying this criterion may not exist even without connectivity constraints, i.e., if the graph of goods is complete. In view of this, it is natural to seek approximate allocations that guarantee each agent a connected bundle of goods with value at least a constant fraction of the maximin share value to the agent. It is known that for some classes of graphs, such as complete graphs, cycles, and $d$-claw-free graphs for any fixed $d$, such approximate allocations indeed exist. However, it is an open problem whether they exist for the class of all graphs. In this paper, we continue the systematic study of the existence of approximate allocations on restricted graph classes. In particular, we show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.