A clique in a graph is strong if it intersects all maximal independent sets. A graph is localizable if it has a partition of the vertex set into strong cliques. Localizable graphs were introduced by Yamashita and Kameda in 1999 and form a rich class of well-covered graphs that coincides with the class of well-covered graphs within the class of perfect graphs. In this paper, we give several equivalent formulations of the property of localizability and develop polynomially testable characterizations of localizable graphs within three non-perfect graph classes: triangle-free graphs, C4-free graphs, and line graphs. Furthermore, we use localizable graphs to construct an infinite family of counterexamples to a conjecture due to Zaare-Nahandi about k-partite well-covered graphs having all maximal cliques of size k.
COBISS.SI-ID: 1540211908
A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. A graph G is H-free for some graph H if G contains no induced subgraph isomorphic to H. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is known to be NP-complete even for very restricted graph classes such as for claw-free graphs, for 2P3-free chordal graphs (and thus, for P7-free graphs), and for bipartite graphs. For the complexity of ED and its weighted version WED, a dichotomy for H-free graphs was reached: A graph H is called a linear forest if H is acyclic and claw-free, that is, if all its components are paths. Thus, the ED problem remains NP-complete for H-free graphs whenever H is not a linear forest. For every linear forest H, WED is either solvable in polynomial time or NP-complete for H-free graphs; the final result showed that WED is solvable in polynomial time for P6-free graphs. For (H1, H2)-free graphs, however, we are still far away from a dichotomy result. The main topics of this paper are: (1) to improve the time bounds and simplify the proofs (based on modular decomposition) for polynomial time cases of WED for some H-free graph classes; (2) to investigate the complexity of WED for some cases of (H1, H2)-free graphs such that WED is NP-complete for H_i-free graphs for at least one of i ? {1, 2}. Since it is well known that WED is solvable in polynomial time for graph classes of bounded clique-width, we consider only classes of (H1, H2)-free graphs with unbounded clique-width.
COBISS.SI-ID: 1540387780
An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of K_4 (the complete graph on four vertices). A wheel is a graph that consists of a chordless cycle, together with a vertex that has at least three neighbors in the cycle. A graph is {ISK4,wheel}-free if it has no ISK4 and does not contain a wheel as an induced subgraph. We give an O(|V(G)|^7)-time algorithm to compute the maximum weight of a stable set in an input weighted {ISK4,wheel}-free graph G with non-negative integer weights.
COBISS.SI-ID: 17896793
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 sP_2-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.
COBISS.SI-ID: 18180441
Motivated by applications in cancer genomics and following the work of Hajirasouliha and Raphael (WABI 2014), Hujdurović et al. (IEEE TCBB, 2018) 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 possible number of rows among all matrices with this property. Hajirasouliha and Raphael also proposed the study of a similar problem, in which the task is to minimize the number of distinct rows of the resulting matrix. Hujdurović 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 give new, more transparent formulations of the two problems, showing that the problems are equivalent to two optimization problems on ranchings in a derived directed acyclic graph. Building on these formulations, we obtain new results on the two problems, including (1) a strengthening of the heuristic by Hujdurović et al. via a new min-max result in digraphs generalizing Dilworth’s theorem, which may be of independent interest; (2) APX-hardness results for both problems; (3) approximation algorithms; and (4) exponential-time algorithms solving the two problems to optimality faster than the naive brute-force approach. Our work relates to several well-studied notions in combinatorial optimization: chain partitions in partially ordered sets, laminar hypergraphs, and (classical and weighted) colorings of graphs.
COBISS.SI-ID: 1540282052