People sometimes act differently when making decisions affecting the present moment versus decisions affecting the future only. This is referred to as time-inconsistent behaviour, and can be modeled as agents exhibiting present bias. A resulting phenomenon is abandonment, which is when an agent initially pursues a task, but ultimately gives up before reaping the rewards. With the introduction of the graph-theoretic time-inconsistent planning model due to Kleinberg and Oren, it has been possible to investigate the computational complexity of how a task designer best can support a present-biased agent in completing the task. In this paper, we study the complexity of finding a choice reduction for the agent; that is, how to remove edges and vertices from the task graph such that a present-biased agent will remain motivated to reach his target even for a limited reward. While this problem is NP-complete in general, this is not necessarily true for instances which occur in practice, or for solutions which are of interest to task designers. For instance, a task designer may desire to find the best task graph which is not too complicated. We therefore investigate the problem of finding simple motivating subgraphs. These are structures where the agent will modify his plan at most k times along the way. We quantify this simplicity in the time-inconsistency model as a structural parameter: The number of branching vertices (vertices with out-degree at least 2) in a minimal motivating subgraph. Our results are as follows: We give a linear algorithm for finding an optimal motivating path, i. e. when k = 0. On the negative side, we show that finding a simple motivating subgraph is NP-complete even if we allow only a single branching vertex — revealing that simple motivating subgraphs are indeed hard to find. However, we give a pseudo-polynomial algorithm for the case when k is fixed and edge weights are rationals, which might be a reasonable assumption in practice.

Abstract A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class $${\mathscr {G}}$$ G , is there a subgraph complement of G which is in $${\mathscr {G}}$$ G ? We show that this problem can be solved in polynomial time for various choices of the graphs class $${\mathscr {G}}$$ G , such as bipartite, d-degenerate, or cographs. We complement these results by proving that the problem is $${{\mathrm{NP}}}$$ NP -complete when $${\mathscr {G}}$$ G is the class of regular graphs.

We generalize the family of (σ,ρ) problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as Distance-r Dominating Set and Distance-r Independent Set. We show that these distance problems are in XP parameterized by the structural parameter mim-width, and hence polynomial-time solvable on graph classes where mim-width is bounded and quickly computable, such as k-trapezoid graphs, Dilworth k-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, k-polygon graphs, circular arc graphs, complements of d-degenerate graphs, and H-graphs if given an H-representation. We obtain these results by showing that taking any power of a graph never increases its mim-width by more than a factor of two. To supplement these findings, we show that many classes of (σ,ρ) problems are W[1]-hard parameterized by mim-width + solution size. We show that powers of graphs of tree-width w−1 or path-width w and powers of graphs of clique-width w have mim-width at most w. These results provide new classes of bounded mim-width. We prove a slight strengthening of the first statement which implies that, surprisingly, Leaf Power graphs which are of importance in the field of phylogenetic studies have mim-width at most 1.

We generalize the family of $(σ, ρ)$-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-$r$ dominating set and distance-$r$ independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as $k$-trapezoid graphs, Dilworth $k$-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, $k$-polygon graphs, circular arc graphs, complements of $d$-degenerate graphs, and $H$-graphs if given an $H$-representation. To supplement these findings, we show that many classes of (distance) $(σ, ρ)$-problems are W[1]-hard parameterized by mim-width + solution size.