Search

We consider the task of allocating indivisible items to agents, when each agent’s preferences are captured by means of a directed acyclic graph. The vertices of such a graph represent items and an arc (a, b) means that the respective agent prefers item a over item b. The dissatisfaction of an agent is measured by the number of non-assigned items which are desired by the agent and for which no more preferred item is given to the agent. The aim is to allocate the items to the agents in a way that minimizes (i) the total dissatisfaction over all agents, or (ii) the maximum dissatisfaction among the agents. For both problems we study the status of computational complexity and obtain NP-hardness results as well as polynomial algorithms with respect to different underlying graph structures, such as trees, stars, paths, and matchings.

The question of characterizing graphs H such that the Vertex Cover problem is solvable in polynomial time in the class of H-free graphs is notoriously difficult and still widely open. We completely solve the corresponding question for a distance-based generalization of vertex cover called distance-k vertex cover, for any positive integer k. In this problem the task is to determine, given a graph G and an integer \(\ell \), whether G contains a set of at most \(\ell \) vertices such that each edge of G is at distance at most k from a vertex in the set. We show that for all \(k \ge 1\) and all graphs H, the distance-k vertex cover problem is solvable in polynomial time in the class of H-free graphs if H is an induced subgraph of \(P_{2k+2} + sP_{\max \{k,2\}}\) for some \(s \ge 0\), and NP-complete otherwise.

In this work we add a graph theoretical perspective to a classical problem of fairly allocating indivisible items to several agents. Agents have different profit valuations of items and we allow an incompatibility relation between pairs of items described in terms of a conflict graph. Hence, every feasible allocation of items to the agents corresponds to a partial coloring, that is, a collection of pairwise disjoint independent sets. The sum of profits of vertices/items assigned to one color/agent should be optimized in a maxi-min sense. We derive complexity and algorithmic results for this problem, which is a generalization of the classical Partition and Independent Set problems. In particular, we show that the problem is strongly NP-complete in the classes of bipartite graphs and their line graphs, and solvable in pseudo-polynomial time in the classes of cocomparability graphs and biconvex bipartite graphs.

Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from an edge-weighted graph by removing all sufficiently light edges. This naturally leads to a generalization of the concept of a graph class to the weighted case by requiring that all level graphs belong to the class. We examine some types of monotonicity of graph classes, such as sandwich monotonicity, to construct edge elimination schemes of edge-weighted graphs. This leads to linear-time recognition algorithms of weighted graphs for which all level graphs are split, threshold, or chain graphs.

A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems remain intractable when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques?

Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes in which this condition is also sufficient, which we call \((\text {tw},\omega )\)-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and k-coloring problems. We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs H for which the class of graphs excluding H is \((\text {tw},\omega )\)-bounded. Our results imply that the class of 1-perfectly orientable graphs is \((\text {tw},\omega )\)-bounded, answering a question of Bresar, Hartinger, Kos, and Milanic from 2018. We also reveal some further algorithmic implications of \((\text {tw},\omega )\)-boundedness related to list k-coloring and clique problems.

Minimal separators in graphs are an important concept in algorithmic graph theory. In particular, many problems that are NP-hard for general graphs are known to become polynomial-time solvable for classes of graphs with a polynomially bounded number of minimal separators. Several well-known graph classes have this property, including chordal graphs, permutation graphs, circular-arc graphs, and circle graphs. We perform a systematic study of the question which classes of graphs defined by small forbidden induced subgraphs have a polynomially bounded number of minimal separators. We focus on sets of forbidden induced subgraphs with at most four vertices and obtain an almost complete dichotomy, leaving open only two cases.

We consider the independent set problem, a classical NP-hard optimization problem that remains hard even under substantial restrictions on the input graphs. The complexity status of the problem is unknown for the classes of \(P_k\)-free graphs for all \(k\ge 7\) and for the class of even-hole-free graphs, that is, graphs not containing any even induced cycles. Using the technique of augmenting graphs we show that the independent set problem is solvable in polynomial time in the class of even-hole-free graphs not containing an induced path on 10 vertices. Our result is developed in the context of the more general class of \(\{P_{10},C_4,C_6\}\)-free graphs.

A vertex v in a graph G is said to be avoidable if every induced two-edge path with midpoint v is contained in an induced cycle. Generalizing Dirac’s theorem on the existence of simplicial vertices in chordal graphs, Ohtsuki et al. proved in 1976 that every graph has an avoidable vertex. In a different generalization, Chvatal et al. gave in 2002 a characterization of graphs without long induced cycles based on the concept of simplicial paths. We introduce the concept of avoidable induced paths as a common generalization of avoidable vertices and simplicial paths. We propose a conjecture that would unify the results of Ohtsuki et al. and of Chvatal et al. The conjecture states that every graph that has an induced k-vertex path also has an avoidable k-vertex path. We prove that every graph with an edge has an avoidable edge, thus establishing the case \(k = 2\) of the conjecture. Furthermore, we point out a close relationship between avoidable vertices in a graph and its minimal triangulations and identify new algorithmic uses of avoidable vertices. More specifically, applying Lexicographic Breadth First Search and bisimplicial elimination orderings, we derive a polynomial-time algorithm for the maximum weight clique problem in a class of graphs generalizing the class of 1-perfectly orientable graphs and its subclasses chordal graphs and circular-arc graphs.

Given a positive integer k, a k-dominating set in a graph G is a set of vertices such that every vertex not in the set has at least k neighbors in the set. A total k-dominating set, also known as a k-tuple total dominating set, is a set of vertices such that every vertex of the graph has at least k neighbors in the set. The problems of finding the minimum size of a k-dominating, resp. total k-dominating set, in a given graph, are referred to as k-domination, resp. total k-domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total k-domination). On the other hand, it follows from recent work by Kang et al. (2017) that these two families of problems are solvable in time \(\mathcal {O}(|V(G)|^{6k+4})\) in the class of interval graphs. In this work, we develop faster algorithms for k-domination and total k-domination in the class of proper interval graphs. The algorithms run in time \(\mathcal {O}(|V(G)|^{3k})\) for each fixed \(k\ge 1\) and are also applicable to the weighted case.

Motivated by applications in cancer genomics and following the work of Hajirasouliha and Raphael (WABI 2014), Hujdurovic et al. (IEEE TCBB, to appear) introduced the minimum conflict-free row split (MCRS) problem: split each row of a given binary matrix into a bitwise OR of a set of rows so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number of rows among all matrices with this property. Hajirasouliha and Raphael also proposed the study of a similar problem, referred to as the minimum distinct conflict-free row split (MDCRS) problem, in which the task is to minimize the number of distinct rows of the resulting matrix. Hujdurovic et al. proved that both problems are NP-hard, gave a related characterization of transitively orientable graphs, and proposed a polynomial-time heuristic algorithm for the MCRS problem based on coloring cocomparability graphs.

We introduce the graph parameter readability and study it as a function of the number of vertices in a graph. Given a digraph \(D\), an injective overlap labeling assigns a unique string to each vertex such that there is an arc from \(x\) to \(y\) if and only if \(x\) properly overlaps \(y\). The readability of \(D\) is the minimum string length for which an injective overlap labeling exists. In applications that utilize overlap digraphs (e.g., in bioinformatics), readability reflects the length of the strings from which the overlap digraph is constructed. We study the asymptotic behaviour of readability by casting it in purely graph theoretic terms (without any reference to strings). We prove upper and lower bounds on readability for certain graph families and general graphs.