Source author record

Andreas Brandstadt

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

9works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Bounded Clique-Width of ( $S_{1,2,2}$ ,Triangle)-Free Graphs

If a graph has no induced subgraph isomorphic to $H_1$ or $H_2$ then it is said to be ( $H_1,H_2$ )-free. Dabrowski and Paulusma found 13 open cases for the question whether the clique-width of ( $H_1,H_2$ )-free graphs is bounded. One of them is the class of ( $S_{1,2,2}$ ,triangle)-free graphs. In this paper we show that these graphs have bounded clique-width. Thus, also ( $P_1+2P_2$ ,triangle)-free graphs have bounded clique-width which solves another open problem of Dabrowski and Paulusma. Meanwhile we were informed by Paulusma that in December 2015, Dabrowski, Dross and Paulusma showed that ( $S_{1,2,2}$ ,triangle)-free graphs (and some other graph classes) have bounded clique-width.

preprint2016arXiv

Dominating Induced Matchings for $P_8$ -free Graphs in Polynomial Time

Let $G=(V,E)$ be a finite undirected graph. An edge set $E' \subseteq E$ is a dominating induced matching (d.i.m.) in $G$ if every edge in $E$ is intersected by exactly one edge of $E'$ . The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in $G$ ; this problem is also known as the Efficient Edge Domination problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three and is solvable in linear time for $P_7$ -free graphs. However, its complexity was open for $P_k$ -free graphs for any $k \ge 8$ ; $P_k$ denotes the chordless path with $k$ vertices and $k-1$ edges. We show in this paper that the weighted DIM problem is solvable in polynomial time for $P_8$ -free graphs.

preprint2016arXiv

Maximum Weight Independent Set in lClaw-Free Graphs in Polynomial Time

The Maximum Weight Independent Set (MWIS) problem is a well-known NP-hard problem. For graphs $G_1, G_2$ , $G_1+G_2$ denotes the disjoint union of $G_1$ and $G_2$ , and for a constant $l \ge 2$ , $lG$ denotes the disjoint union of $l$ copies of $G$ . A {\em claw} has vertices $a,b,c,d$ , and edges $ab,ac,ad$ . MWIS can be solved for claw-free graphs in polynomial time; the first two polynomial time algorithms were introduced in 1980 by \cite{Minty1980,Sbihi1980}, then revisited by \cite{NakTam2001}, and recently improved by \cite{FaeOriSta2011,FaeOriSta2014}, and by \cite{NobSas2011,NobSas2015} with the best known time bound in \cite{NobSas2015}. Furthermore MWIS can be solved for the following extensions of claw-free graphs in polynomial time: fork-free graphs \cite{LozMil2008}, $K_2$ +claw-free graphs \cite{LozMos2005}, and apple-free graphs \cite{BraLozMos2010,BraKleLozMos2008}. This manuscript shows that for any constant $l$ , MWIS can be solved for $l$ claw-free graphs in polynomial time. Our approach is based on Farber's approach showing that every $2K_2$ -free graph has ${\cal O}(n^2)$ maximal independent sets \cite{Farbe1989}, which directly leads to a polynomial time algorithm for MWIS on $2K_2$ -free graphs by dynamic programming. Solving MWIS for $l$ claw-free graphs in polynomial time extends known results for claw-free graphs, for $lK_2$ -free graphs for any constant $l$ \cite{Aleks1991,FarHujTuz1993,Prisn1995,TsuIdeAriShi1977}, for $K_2$ +claw-free graphs, for $2P_3$ -free graphs \cite{LozMos2012}, and solves the open questions for $2K_2+P_3$ -free graphs and for $P_3$ +claw-free graphs being two of the minimal graph classes, defined by forbidding one induced subgraph, for which the complexity of MWIS was an open problem.

preprint2016arXiv

Maximum Weight Independent Sets for ( $P_7$ ,Triangle)-Free Graphs in Polynomial Time

The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity was an open problem for $P_k$ -free graphs, $k \ge 5$ . Recently, Lokshtanov, Vatshelle, and Villanger proved that MWIS can be solved in polynomial time for $P_5$ -free graphs, and Lokshtanov, Pilipczuk, and van Leeuwen proved that MWIS can be solved in quasi-polynomial time for $P_6$ -free graphs. It still remains an open problem whether MWIS can be solved in polynomial time for $P_k$ -free graphs, $k \geq 6$ or in quasi-polynomial time for $P_k$ -free graphs, $k \geq 7$ . Some characterizations of $P_k$ -free graphs and some progress are known in the literature but so far did not solve the problem. In this paper, we show that MWIS can be solved in polynomial time for ( $P_7$ ,triangle)-free graphs. This extends the corresponding result for ( $P_6$ ,triangle)-free graphs and may provide some progress in the study of MWIS for $P_7$ -free graphs.

preprint2015arXiv

Weighted Efficient Domination for $P_5$ -Free Graphs in Linear Time

In a finite undirected graph $G=(V,E)$ , a vertex $v \in V$ {\em dominates} itself and its neighbors. A vertex set $D \subseteq V$ in $G$ is an {\em efficient dominating set} ({\em e.d.} for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$ . The {\em Efficient Domination} (ED) problem, which asks for the existence of an e.d. in $G$ , is known to be NP-complete for $P_7$ -free graphs but solvable in polynomial time for $P_5$ -free graphs. Very recently, it has been shown by Lokshtanov et al. and independently by Mosca that ED is solvable in polynomial time for $P_6$ -free graphs. In this note, we show that, based on modular decomposition, ED is solvable in linear time for $P_5$ -free graphs.

preprint2015arXiv

Weighted Efficient Domination for $P_6$ -Free Graphs in Polynomial Time

In a finite undirected graph $G=(V,E)$ , a vertex $v \in V$ {\em dominates} itself and its neighbors in $G$ . A vertex set $D \subseteq V$ is an {\em efficient dominating set} ({\em e.d.} for short) of $G$ if every $v \in V$ is dominated in $G$ by exactly one vertex of $D$ . The {\em Efficient Domination} (ED) problem, which asks for the existence of an e.d. in $G$ , is known to be NP-complete for $P_7$ -free graphs but solvable in polynomial time for $P_5$ -free graphs. The $P_6$ -free case was the last open question for the complexity of ED on $F$ -free graphs. Recently, Lokshtanov, Pilipczuk and van Leeuwen showed that weighted ED is solvable in polynomial time for $P_6$ -free graphs, based on their sub-exponential algorithm for the Maximum Weight Independent Set problem for $P_6$ -free graphs. Independently, at the same time, Mosca found a polynomial time algorithm for weighted ED on $P_6$ -free graphs using a direct approach. In this paper, we describe the details of this approach which is simpler and much faster, namely its time bound is ${\cal O}(n^6 m)$ .

preprint2015arXiv

Weighted Efficient Domination in Classes of $P_6$ -free Graphs

In a graph $G$ , an efficient dominating set is a subset $D$ of vertices such that $D$ is an independent set and each vertex outside $D$ has exactly one neighbor in $D$ . The Minimum Weight Efficient Dominating Set (Min-WED) problem asks for an efficient dominating set of total minimum weight in a given vertex-weighted graph; the Maximum Weight Efficient Dominating Set (Max-WED) problem is defined similarly. The Min-WED/Max-WED is known to be $NP$ -complete for $P_7$ -free graphs, and is known to be polynomial time solvable for $P_5$ -free graphs. However, the computational complexity of the Min-WED/Max-WED problem is unknown for $P_6$ -free graphs. In this paper, we show that the Min-WED/Max-WED problem can be solved in polynomial time for two subclasses of $P_6$ -free graphs, namely for ( $P_6,S_{1,1,3}$ )-free graphs, and for ( $P_6$ , bull)-free graphs.

preprint2014arXiv

Weighted Efficient Domination for $(P_5+kP_2)$ -Free Graphs in Polynomial Time

Let $G$ be a finite undirected graph. A vertex {\em dominates} itself and all its neighbors in $G$ . A vertex set $D$ is an {\em efficient dominating set} (\emph{e.d.}\ for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$ . The \emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d.\ in $G$ , is known to be \NP-complete even for very restricted graph classes such as for claw-free graphs, for chordal graphs and for $2P_3$ -free graphs (and thus, for $P_7$ -free graphs). We call a graph $F$ a {\em linear forest} if $F$ is cycle- and claw-free, i.e., its components are paths. Thus, the ED problem remains \NP-complete for $F$ -free graphs, whenever $F$ is not a linear forest. Let WED denote the vertex-weighted version of the ED problem asking for an e.d. of minimum weight if one exists. In this paper, we show that WED is solvable in polynomial time for $(P_5+kP_2)$ -free graphs for every fixed $k$ , which solves an open problem, and, using modular decomposition, we improve known time bounds for WED on $(P_4+P_2)$ -free graphs, $(P_6,S_{1,2,2})$ -free graphs, and on $(2P_3,S_{1,2,2})$ -free graphs and simplify proofs. For $F$ -free graphs, the only remaining open case is WED on $P_6$ -free graphs.

preprint2011arXiv

Dominating Induced Matchings for P7-Free Graphs in Linear Time

Let $G$ be a finite undirected graph with edge set $E$ . An edge set $E' \subseteq E$ is an {\em induced matching} in $G$ if the pairwise distance of the edges of $E'$ in $G$ is at least two; $E'$ is {\em dominating} in $G$ if every edge $e \in E \setminus E'$ intersects some edge in $E'$ . The \emph{Dominating Induced Matching Problem} (\emph{DIM}, for short) asks for the existence of an induced matching $E'$ which is also dominating in $G$ ; this problem is also known as the \emph{Efficient Edge Domination} Problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three. However, its complexity was open for $P_k$ -free graphs for any $k \ge 5$ ; $P_k$ denotes a chordless path with $k$ vertices and $k-1$ edges. We show in this paper that the weighted DIM problem is solvable in linear time for $P_7$ -free graphs in a robust way.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Andreas Brandstadt

Research overview

Is this your work?

9 publications

Bounded Clique-Width of ( $S_{1,2,2}$ ,Triangle)-Free Graphs

Dominating Induced Matchings for $P_8$ -free Graphs in Polynomial Time

Maximum Weight Independent Set in lClaw-Free Graphs in Polynomial Time

Maximum Weight Independent Sets for ( $P_7$ ,Triangle)-Free Graphs in Polynomial Time

Weighted Efficient Domination for $P_5$ -Free Graphs in Linear Time

Weighted Efficient Domination for $P_6$ -Free Graphs in Polynomial Time

Weighted Efficient Domination in Classes of $P_6$ -free Graphs

Weighted Efficient Domination for $(P_5+kP_2)$ -Free Graphs in Polynomial Time

Dominating Induced Matchings for P7-Free Graphs in Linear Time

See the researcher in context

Building this map preview

Andreas Brandstadt

Research overview

Is this your work?

9 publications

Bounded Clique-Width of (S1,2,2S_{1,2,2}S1,2,2​,Triangle)-Free Graphs

Dominating Induced Matchings for P8P_8P8​-free Graphs in Polynomial Time

Maximum Weight Independent Set in lClaw-Free Graphs in Polynomial Time

Maximum Weight Independent Sets for (P7P_7P7​,Triangle)-Free Graphs in Polynomial Time

Weighted Efficient Domination for P5P_5P5​-Free Graphs in Linear Time

Weighted Efficient Domination for P6P_6P6​-Free Graphs in Polynomial Time

Weighted Efficient Domination in Classes of P6P_6P6​-free Graphs

Weighted Efficient Domination for (P5+kP2)(P_5+kP_2)(P5​+kP2​)-Free Graphs in Polynomial Time

Dominating Induced Matchings for P7-Free Graphs in Linear Time

See the researcher in context

Building this map preview

Bounded Clique-Width of ( $S_{1,2,2}$ ,Triangle)-Free Graphs

Dominating Induced Matchings for $P_8$ -free Graphs in Polynomial Time

Maximum Weight Independent Sets for ( $P_7$ ,Triangle)-Free Graphs in Polynomial Time

Weighted Efficient Domination for $P_5$ -Free Graphs in Linear Time

Weighted Efficient Domination for $P_6$ -Free Graphs in Polynomial Time

Weighted Efficient Domination in Classes of $P_6$ -free Graphs

Weighted Efficient Domination for $(P_5+kP_2)$ -Free Graphs in Polynomial Time