We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. Just like ...their original counterparts, these variants are NP-complete for general graphs. A graph G is H-free for some graph H if G contains no induced subgraph isomorphic to H. It is known that Connected Vertex Cover is NP-complete even for H-free graphs if H contains a claw or a cycle. We show that the two other connected variants also remain NP-complete if H contains a cycle or claw. In the remaining case H is a linear forest. We show that Connected Vertex Cover, Connected Feedback Vertex Set, and Connected Odd Cycle Transversal are polynomial-time solvable for sP2-free graphs for every constant s≥1. For proving these results we use known results on the price of connectivity for vertex cover, feedback vertex set, and odd cycle transversal. This is the first application of the price of connectivity that results in polynomial-time algorithms.
Strong cliques in diamond-free graphs Chiarelli, Nina; Martínez-Barona, Berenice; Milanič, Martin ...
Theoretical computer science,
02/2021, Volume:
858
Journal Article
Peer reviewed
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 all remain NP-hard or co-NP-hard 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?
On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamond-free graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.
•A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets.•We study strong cliques in the class of diamond-free graphs.•We characterize diamond-free CIS graphs and study their Erdős-Hajnal property.•We characterize co-strongly perfect diamond-free graphs.•We derive hardness results for five related problems.
We consider the fair allocation of indivisible items to several agents and add a graph theoretical perspective to this classical problem. Namely, we introduce an incompatibility relation between ...pairs of items described in terms of a conflict graph. Every subset of items assigned to one agent has to form an independent set in this graph. Thus, the allocation of items to the agents corresponds to a partial coloring of the conflict graph. Every agent has its own profit valuation for every item. Aiming at a fair allocation, our goal is the maximization of the lowest total profit of items allocated to any one of the agents. The resulting optimization problem contains, as special cases, both
Partition
and
Independent Set
. In our contribution we derive complexity and algorithmic results depending on the properties of the given graph. We show that the problem is strongly NP-hard for bipartite graphs and their line graphs, and solvable in pseudo-polynomial time for the classes of chordal graphs, cocomparability graphs, biconvex bipartite graphs, and graphs of bounded treewidth. Each of the pseudo-polynomial algorithms can also be turned into a fully polynomial approximation scheme (FPTAS).
This paper studies the allocation of indivisible items to agents, when each agent’s preferences are expressed by means of a directed acyclic graph. The vertices of each preference graph represent the ...subset of items approved of by the respective agent. An arc (a,b) in such a graph means that the respective agent prefers item a over item b. We introduce a new measure of dissatisfaction of an agent by counting the number of non-assigned items which are approved of by the agent and for which no more preferred item is allocated to the agent. Considering two problem variants, we seek an allocation of 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 optimization problems we study the status of computational complexity and obtain NP-hardness results as well as polynomial algorithms with respect to natural underlying graph structures, such as stars, trees, paths, and matchings. We also analyze the parameterized complexity of the two problems with respect to various parameters related to the number of agents, the dissatisfaction threshold, the vertex degrees of the preference graphs, and the treewidth.
A total dominating set in a graph is a subset of vertices such that every vertex in the graph has a neighbor in it. A graph is said to be total domishold if it admits a total domishold structure, ...that is, a hyperplane with non-negative coefficients that separates the characteristic vectors of its total dominating sets from the characteristic vectors of other vertex subsets. Hereditary total domishold graphs, that is, graphs every induced subgraph of which is total domishold, were recently characterized in terms of forbidden induced subgraphs; this characterization leads to an O(|V(G)|6) recognition algorithm of hereditary total domishold graphs.
In this paper, we study a subclass G of the hereditary total domishold graphs obtained by replacing two of the forbidden induced subgraphs of order 6 with two of their proper induced subgraphs of order 5. We show that every connected graph in G is a leaf extension of a threshold graph, that is, it can be obtained from some threshold graph G by attaching some pendant vertices to each vertex of G. Using this property, we develop a structural characterization of graphs in G, which implies a linear time recognition algorithm for graphs in this class. We also give a linear time algorithm for computing a total domishold structure of a graph in G. In contrast to the algorithm for the general case of (hereditary) total domishold graphs, which relies on solving a linear program, our algorithm is purely combinatorial and works directly with the graph.
A total dominating set in a graph is a set of vertices such that every vertex of the graph has a neighbor in the set. We introduce and study graphs that admit non-negative real weights associated to ...their vertices such that a set of vertices is a total dominating set if and only if the sum of the corresponding weights exceeds a certain threshold. We show that these graphs, which we call total domishold graphs, form a non-hereditary class of graphs properly containing the classes of threshold graphs and the complements of domishold graphs, and are closely related to threshold Boolean functions and threshold hypergraphs. We present a polynomial time recognition algorithm of total domishold graphs, and characterize graphs in which the above property holds in a hereditary sense. Our characterization is obtained by studying a new family of hypergraphs, defined similarly as the Sperner hypergraphs, which may be of independent interest.
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 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, respectively total k-dominating set, in a given graph, are referred to as k-domination, respectively 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 previous works by Bui-Xuan et al. (2013) 8 and by Belmonte and Vatshelle (2013) 3 that these two families of problems are solvable in time O(|V(G)|3k+4) in the class of interval graphs. We develop faster algorithms for k-domination and total k-domination in the class of proper interval graphs, by means of reduction to a single shortest path computation in a derived directed acyclic graph with O(|V(G)|2k) nodes and O(|V(G)|4k) arcs. We show that a suitable implementation, which avoids constructing all arcs of the digraph, leads to a running time of O(|V(G)|3k). The algorithms are also applicable to the weighted case.
Recently, Milanič and Trotignon introduced the class of equistarable graphs as graphs without isolated vertices admitting positive weights on the edges such that a subset of edges is of total weight ...1 if and only if it forms a maximal star. Based on equistarable graphs, counterexamples to three conjectures on equistable graphs were constructed, in particular to Orlin’s conjecture, which states that every equistable graph is a general partition graph.
In this paper we characterize equistarable bipartite graphs. We show that a bipartite graph is equistarable if and only if every 2-matching of the graph extends to a matching covering all vertices of degree at least 2. As a consequence of this result, we obtain that Orlin’s conjecture holds within the class of complements of line graphs of bipartite graphs.
We also connect equistarable graphs to the triangle condition, a combinatorial condition known to be necessary (but in general not sufficient) for equistability. We show that the triangle condition implies general partitionability for complements of line graphs of forests, and construct an infinite family of triangle non-equistable graphs within the class of complements of line graphs of bipartite graphs.
We consider the fair allocation of indivisible items to several agents with additional conflict constraints. These are represented by a conflict graph where each item corresponds to a vertex of the ...graph and edges in the graph represent incompatible pairs of items which should not be allocated to the same agent. This setting combines the issues of P
artition
and I
ndependent
S
et
and can be seen as a partial coloring of the conflict graph. In the resulting optimization problem, each agent has its own valuation function for the profits of the items. We aim at maximizing the lowest total profit obtained by any of the agents. In a previous paper, this problem was shown to be strongly NP-hard for several well-known graph classes, e.g., bipartite graphs and their line graphs. On the other hand, it was shown that pseudo-polynomial time algorithms exist for the classes of chordal graphs, cocomparability graphs, biconvex bipartite graphs, and graphs of bounded treewidth. In this contribution, we extend this line of research by developing pseudo-polynomial time algorithms that solve the problem for the class of convex bipartite conflict graphs, graphs of bounded clique-width, and graphs of bounded tree-independence number. The algorithms are based on dynamic programming and also permit fully polynomial-time approximation schemes (FPTAS).